Array search알고리즘의 Optimality

n개 원소를 갖는 배열 E와 정수 K가 주어진다. K=E[index]인 인덱스를 찾고, 없으면 -1을 리턴하라.

 

1. A: unsorted Array일 때, 순차적 탐색

• W(n) = n  (Worst case)
• A(n) = q[(n+1)/2]+(1-q)n   (Average case. q:탐색에 성공할 확률)
• unsorted일 때 F(n)=n 이므로 알고리즘 A는 optimal

2. B:  오름차순 정렬된 배열일 때, 순차적 탐색

• W(n) = n
• A(n) = q[(n+1)/2]+(1-q)n 
• 배열이 정렬되었다는 정보를 이용하지 않음. optimal X

 

3. C: 오름차순 정렬된 배열일 때, 순차적 탐색하다가 K보다 큰 원소를 만나면 -1 리턴 (찾는 원소가 없다)

• W(n) = n+1 => n
• Asucc(n) = Σ(1/(n+1))(i+1) = (1/n)[n(n+1)/2] = (n+1)/2
• Afail(n) = Σ(1/(n+1))(i+1)+n/(n+1) = n/2+n(n+1)      (n/(n+1)은 K가 그 어떤 배열의 원소보다도 클 때)
• A(n) = q(1+n)/2 + (1-q)(n/(n+1)+n/2) => n/2

4. Binary Search

• 재귀함수 호출 횟수는 log2n에 비례한다.
• W(n) ∈ Θ(logn)
• Asucc(n) = log(n+1) - 1 + log(n+1)/n
• Afail(n) = log(n+1) 
• A(n) = q(log(n+1) - 1 + log(n+1)/n) + (1-q)(log(n+1)) = log(n+1) - q  (q는 무시 가능) 

 

Optimality of Binary Search

• 문제 복잡도 분석을 위해 Decision Tree를 이용한다.
• Worst case에서의 비교 연산의 수는 root->leaf로 가는 가장 긴 경로의 노드 수와 같다. 이를 p라고 하자.
• decision tree가 N개의 노드를 갖는다고 가정하면
• N<= 1+2+4+...+2^(p-1) = 2^p - 1
• 2^p >= (N+1)
• N>=n. 즉, 0~(n-1)범위에 label이 i인 노드가 decision tree에 반드시 존재한다.

 

N>=n임을 Contradiction을 이용해서 증명하자. (N:노드의 수, n:인풋 배열의 길이. N<n을 가정하고 모순임을 보인다)

• 0~(n-1) 범위 내에 label이 i인 노드가 존재하지 않는다고 가정한다.
• E1, E2 두 개의 배열이 있다고 할 때, 다음을 가정한다.
  1. 두 배열은 i번째에 있는 값을 제외하곤 모두 같은 값을 가진다.
  2. E1[i]=K 지만 E2[i]=K' > K
  3. 모든 j<i에 대해 E1[j]=E2[j] using key value < K
  4. 모든 j<i에 대해 E1[j]=E2[j] using key value > K'
• decision tree에는 i번째 레이블이 존재하지 않는다. (N<n이라고 가정했고, 그 중에 i가 존재하지 않는다고 가정했으므로)
• 즉, 알고리즘 A는 K를 E1[i]나 E2[i]와 절대 비교하지 않고, 둘에 대해 같은 output을 낸다. ex) E1[i]=50, E[i]=51이고 나머지 원소는 다 같으면 K에 대해서 i번째는 비교하지 않게 되므로 두 배열에 대해 같은 결과가 나옴
• 이러한 알고리즘 A는 최소 한 번의 틀린 output을 내놓기 때문에 incorrect
• 따라서 decision tree는 최소 n 개의 노드를 가진다.

Optimality Result

• 즉, 2^p >= (N+1) >= (n+1)
• p>=log(n+1)  (p: longest path의 노드의 수. 최악의 경우일 때 basic operation 수)
• n개 원소를 갖는 배열에서 K를 찾는 어떤 알고리즘도 최소 ⌈log(n+1)⌉ 번의 비교를 하게 된다.
• 알고리즘 D는 worst case에서 ⌈log(n+1)⌉ 번의 연산을 하므로 optimal.