점근적 표기 / 평균 수행 시간 분석

\(f(n) = \Theta(g(n)) \approx a = b\) \(f(n) = O(g(n)) \approx a \le b\) \(f(n) = \ o(g(n)) \approx a < b\) \(f(n) = \Omega(g(n)) \approx a \ge b\) \(f(n) = \omega(g(n)) \approx a > b\)

\(W(n) = \max{\ t(I)\

\ I \in D_n }\)

평균 수행 시간 분석

\[A(n) = \sum_{I \in D_n} Pr(I)t(I) \] 이는 \(E(x)\)를 구하는 공식과 같은데, 생각해보면 입력\(I\)가 주어졌을 때의 수행 횟수\(t(I)\)들의 평균(기대값)을 구한 것이 평균 복잡도이기 때문이다.

평균 수행 횟수는 \(Pr(I)\)가 어떻게 정의되느냐에 따라 달라지는데, 각각의 \(t(I)\)가 발생할 확률이 모두 동일하다면 간단히 구할 수 있어 별 문제가 되지 않으나, 확률이 다른 경우 분석이 필요하다.

이진 탐색의 경우 트리 안에 있는 값을 입력으로 집어넣을 때, 즉 탐색이 제대로 종료될 때(성공 탐색\(A_1(n)\))와 트리에 없는 값을 입력으로 집어넣어 말단 노드까지 찾다가 못찾았다고 리턴하는 경우(실패 탐색\(A_0(n)\))으로 나눌 수 있다. 평균 수행 횟수는 빨리 탐색이 완료되어 조기종료 될 수록 줄어들기 때문에, 성공 탐색이 발생할 확률이 높을 수록 평균 수행 횟수가 감소 하며 성공 탐색이 발생할 확률이 높다는 것은 트리 안에 있는 값을 입력으로 집어넣을 확률이 높다는 것을 의미한다. 성공 확률이 \(q\)일 때의 평균 비교 횟수를 \(A_q(n)\)이라고 한다면 조건 평균 법칙에 의해 \[A_q(n) = qA_1(n) + (1-q)A_0(n)\] \(n = 2^k-1\)이면, \(A_0(n) = \lg(n+1)\)이라는 점은 조금만 생각해 보면 알 수 있다.

문제는 성공 탐색인데, 이를 분석하기 위해서는 위 식을 약간 변형하는 편이 좋다. 후술했지만 그냥 위 식을 그대로 사용해도 된다. 어떤 특정한 입력\(I_i\)에 대한 수행 횟수\(t(I_i)\)를 정리하는게 아니라, 반대로 각각의 수행 횟수\(t\)에 대해 입력했을 때 이 수행 횟수를 가지는 입력\(I_i\)가 몇 개씩 있는지로 정리하고 이 때 수행 횟수가 \(t\)인 입력의 개수를 \(s_t\)로 한다. 예를 들어 \(I_2\)를 입력받았을 때 수행 횟수가 3이고, 수행 횟수가 3인 입력이 \(I_8, I_{15}, I_{21}\)까지 총 4개라면 수행 횟수가 3인 입력의 개수 \(s_3 = 4\)다. 이진 탐색이므로 \(s_1=2^0, s_2=2^1, s_3=2^2 … s_t=2^{t-1}\)이고, 각 입력에 대한 발생 확률이 \(1/n\)이라고 가정하면 알고리즘이 \(t\)번 수행될 확률은 \(s_t/n\)이다. 따라서 \(t(I) : t, Pr(I) : s_t/n\) 이므로 다음과 같다. ( 또는 평균 \(E(x)\)를 구하는 것을 생각해도 된다. ) \[A(n) = \sum_{t=1}^k t \left( {s_t \over n} \right) = {1 \over n} \sum_{t=1}^k t2^{t-1}\]

이렇게 바꿔서 생각하지 않고 원래 공식을 사용해도 되는데, 맨 처음 배열에서 mid를 판별하기 위한 수행 횟수\(t(I_{mid})\)는 1, 둘로 나뉘어진 배열 각각의 mid를 판별하기 위한 수행 횟수\(t(I_{mid/2||mid3/2})\)는 각각 2이므로 \(2 \times 2\), 넷으로 나뉘어진 배열 각각의 mid를 판별하기 위한 수행 횟수는 각각 3이므로 \(3 \times 4\) … \(2^{k-1}\)로 나뉘어진 배열 각각의 mid를 판별하기 위한 수행 횟수는 각각 \(k\)이므로 \(k \times 2^{k-1}\) 따라서 다음과 같다. \[A(n) = {1 \over n}\sum_{t=1}^k t2^{t-1}\]

산술-기하 급수를 사용하면 다음과 같다. \[A(n) = {1 \over n} \sum_{t=1}^k t2^{t-1} = {(k-1)2^k+1 \over n}\]

산술-기하 급수. 증명은 \(2S_n - S_n\) \[S_n = \sum_{i=1}^k i2^i = (k-1)2^{k+1}+2\]

\(n = 2^k-1\)이므로 이진 탐색에서 성공 탐색에 대한 평균 수행 횟수는 다음과 같다. \[A_1(n) = \lg(n+1) -1 + O({\lg(n) \over n})\]

따라서 성공 탐색 확률에 따른 이진 탐색의 평균 수행 횟수는 \[A_q(n) = \lg(n+1) - q\]