임의의 두 문자열이 같은지 확인하는 데 예상되는 시간 복잡도는 얼마입니까?

Question

간단한(순진한?) 대답은 O(n)입니다. 여기서 n은 더 짧은 문자열의 길이입니다.최악의 경우 모든 문자 쌍을 비교해야 하기 때문입니다.

여태까지는 그런대로 잘됐다.나는 우리 모두가 둘의 동등성을 확인하는 것에 동의할 수 있다고 생각합니다. 같은 길이 문자열에는 O(n) 런타임이 필요합니다.

그러나 많은(대부분?) 언어(Python 3.7을 사용하고 있습니다)는 상수 시간 조회를 허용하기 위해 문자열 길이를 저장합니다.그래서 두 사람의 경우 길이가 같지 않음 문자열을 사용하면 간단히 확인할 수 있습니다 len(string_1) != len(string_2) 일정한 시간에.Python 3가 실제로 이러한 최적화를 수행하는지 확인할 수 있습니다.

이제 두 개의 동등성을 확인하는 경우 진심으로 임의의 문자열(임의의 길이)을 사용하는 경우 문자열의 길이가 같은 경우보다 길이가 다를 가능성이 훨씬 더 높습니다(무한히 있다고 생각합니다).이는 (통계적으로) 거의 항상 일정한 시간에 비교할 수 있도록 보장합니다.

따라서 우리는 O(1) 평균에서 두 개의 임의 문자열을 비교할 수 있으며 매우 드문 최악의 경우 O(n)을 사용할 수 있습니다.해시 테이블 조회를 O(1)로 간주하는 것과 같은 방식으로 문자열 비교를 O(1)로 고려해야 합니까?

Answer 1

작업의 예상되는 시간 복잡도를 논의하려면 입력에 대한 분포를 지정하고, 또한 이것이 의미하는 바를 설명해야 합니다. $n$.

하지만 조심해야 합니다.예를 들어, 최대 20개의 단어 길이에 대한 일종의 분포를 고려하려면 주석의 제안을 고려하십시오.이 경우 문자열 비교는 명확합니다. $O(1)$, 20은 단지 상수이기 때문입니다.이를 방지하는 방법에는 여러 가지가 있습니다.

• 비점근적 시간 복잡도를 요청하세요.시간 복잡도는 계산 모델에 따라 크게 달라지므로 예를 들어 액세스된 입력 메모리 셀 수를 계산할 수 있습니다.

• 매개변수에 따라 입력 분포를 지정할 수 있습니다. $m$, 그런 다음 점근적 복잡성을 요청합니다. $m$.

여기에 예가 있습니다.길이가 임의의 두 이진 문자열인 경우 $n$, 대략 4번의 액세스가 예상됩니다.대조적으로, 문자열이 컬렉션에서 무작위로 선택되면 $0^i1^{n-i}$, 액세스 횟수는 대략 $(2/3)n$.점근 표기법을 사용하더라도 이 두 분포를 분리할 수 있습니다.알고리즘이 실행됩니다 $O(1)$ 첫 번째 배포에서, 그리고 $\세타(n)$ 두 번째에.

또 다른 문제는 다음의 의미이다. $n$.예를 들어 문자열을 고려하십시오. $0^m$, 어디 $m \sim G(1/2)$ 기하확률변수이다.길이 입력에 대해 실행되는 경우 $a,b$, 실행 시간은 $\세타(\min(a,b))$.이것을 어떻게 표현해야 할까요? $n = a+b$?한 가지 선택은 입력 길이가 다음과 같은 경우 예상 실행 시간을 묻는 것입니다. $n$.이 경우,$$ mathbb {e} [ min (a, b)] = sum_ {a = 1}^{n-1} frac {(1/2)^a (1/2)^{n-1 -a}}} { sum_ {a '= 1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a '}} min (a, na ) = frac {1} {n-1} sum_ {a = 1}^{n-1} min (a, na) 대략 frac {n} {4}, $$따라서 예상 실행 시간은 다음과 같습니다. $\세타(n)$.