가장 큰 회문색 부분 문자열 찾기, 알고리즘 복잡도

Question

예를 들어 문자열이 주어졌습니다. "acdfdcqqc"이고 가장 큰 회문 하위 문자열을 찾으려면 알고리즘을 만들어야합니다.이 경우 "cdfdc"입니다. 2n 개의 가능한 시작 각각에 대해

a - c - d - f - d - c - q - q - c 
1 0 1 0 1 0 5 0 1 0 1 0 1 4 1 0 1 

: 그것은 크기 2N의 배열과 중심 즉 대 그 시점에 가장 회문의 길이를 산출 할 때마다 작성하여 O (N^2) 알고리즘을 고안 쉽게 포인트 나는 그 위치에서 시작하는 가장 큰 회상의 길이를 찾는 양방향으로 움직입니다. 따라서 2n 작업 각각에 대해 대부분의 O (n) 작업을 수행하므로 O (n^2) 시간의 복잡성이 발생합니다.

내가 알기 좋아하는 것을 사용하여 선형 시간으로 수행 할 수 있음을 알고 있습니다 : https://en.wikipedia.org/wiki/Longest_palindromic_substring.

그러나 처리중인 문자열이 자연어 텍스트에서 추출되었다고 가정합니다. 영어 텍스트에서 임의로 위치를 선택하면 예상되는 대칭이 매우 낮습니다. 나는 예상되는 공산주의가 각면에서 한 캐릭터보다 적다고 말할 것이다. 따라서, 제 알고리즘이 2n 배의 예상 상수 시간 연산을 수행하여 알고리즘 O (n)을 평균적으로 수행한다고 말할 수 있습니까? O(n) 시간은 모든 가능한 입력 위해 이렇게 않는다는 것을 의미 예상

Answer 1

알고리즘의 예상 실행 시간은 가능한 모든 입력에 대해 알고리즘의 평균 실행 시간입니다. 교과서가 지적했듯이, 이것을 해결하는 것이 항상 쉬운 것은 아니며, 무작위로 선택된 입력에 대한 알고리즘의 실행 시간 인 대안을 사용하는 것이 유용 할 때도 있습니다. 그러나 원칙은 동일합니다. "예상 실행 시간"은 확률값이며 알고리즘의 많은 응용 프로그램에만 집합 적으로 적용됩니다.

대조적으로 "최악의 실행 시간"은 (각 길이의) 모든 입력에 대한 알고리즘의 최악 실행 시간입니다. 또한 계산하기가 항상 쉬운 것은 아니지만 O (f (n))만이 f (n)이 상한값이라고 말하기 때문에 big-O 표기법의 경우에는 상한 계산에 적합합니다. 경계.

제한된 입력 집합에 알고리즘을 적용하는 경우 제한된 집합에 예상되거나 최악의 실행 시간을 지정할 수 있습니다. 입력이 가능한 입력 범위에 균등하게 분배되지 않은 경우 예상 실행 시간을 계산할 때이를 고려해야합니다.

palindrome 길이의 경우, 입력이 영어 텍스트의 무작위로 선택된 부분 문자열 인 경우 가장 큰 회상색의 예상 길이는 다음 중 무작위로 선택한 텍스트의 가장 큰 회상색의 예상 길이보다 약간 (약간) 길어집니다. 소문자와 공백 문자 집합에서 문자를 가져온 문자열의 전체 영역.그러나이 두 입력 집합에 대해 가장 긴 회문문의 예상 길이는 O (1)입니다.

입력 문자열 범위의 특성을 지정해야하지만 알고리즘이 "expected O (n)"이라고 말하는 것이 좋습니다. 알고리즘에 대한 입력을 제어 할 수 없다면, 최악의 경우의 실행 시간도 관련이 있습니다. 순진한 알고리즘에 대해 최악의 경우를 입력하기 쉽기 때문에 DoS 공격이 분명히 가능합니다.

Answer 2

호 알고리즘 설계

는 알고리즘이 실행에 있다고한다. 즉, 입력이 제한된 세트에서 무작위로 균등하게 선택된다는 사실이 아니라 알고리즘의 임의성 (내부 코인 플립)에 대한 기대가 있어야합니다.

그러나 알고리즘이 좋지 않다는 의미는 아닙니다. 입력이 영어 텍스트에만 국한되어있어 일반 입력보다 알고리즘을 빠르게 만드는 특정 속성을 보유한다는 사실을 사용하는 것이 좋습니다. 그러나 사용중인 용어 (예상 O(n) 시간)는 모든 입력에 대해 실행 시간이 O(n) 일 것으로 예상되는 알고리즘을 위해 예약되어 있습니다.