5개로 나눌 때 O 성능 분석

Blum, Floyd, Pratt, Rivest, & Tarjan(1973)의 선택 알고리즘(정확히는 median-of-medians)은 O(n)의 성능으로 순위 통계량(i번째 원소)을 검색할 수 있게 해준다. 이 알고리즘은 n개의 원소를 1) 5개의 집단으로 나누고 각 집단의 중간값(median)을 찾아(Θ(n)) 2) 재귀적으로 _└n/5_┘ 집단의 중간값을 찾는 Select를 호출한다(T(n/5)). 3) 이 중간값을 피봇(pivot) x로 삼고, 원소를 분할(partitioning)한다(Θ(n)). 4) 최악의 경우 x보다 큰(작은) 원소가 ^┌5/2^┐·_└└n/5_┘/2_┘ = 3_└n/10_┘ ≥ n/4개 있으므로(n≥50) n - n/4 = 3n/4개에 대해 재귀호출을 하게 된다(T(3n/4)). 이상에서 T(n) = T(n/5) + T(3n/4) + Θ(n)이고, 강의노트를 참고해 점화식을 풀면 O(n)이 된다. 그런데 이때 집단을 5개가 아니라 3개로 나누면 어떻게 될까? 여전히 O(n)일까?

3개로 나눌 때 O 성능 분석

위의 1)에서 3개의 집단으로 나누고(Θ(n)) 2)에서 _└n/3_┚ 집단의 중간값을 찾으며(T(n/3)) 3)은 동일하다(Θ(n)). 4)에서 최악의 경우 x보다 큰(작은) 원소 ^┌3/2^┐·_└└n/3_┘/2_┘ = 2_└n/6_┘ 개에 대해 재귀호출을 한다. 이때의 성능이O(n)이라고 가정하고 추측확인법(guess & verify)을 적용해보자. n≥6일 때 2_└n/6_┘ ≥ n/6이므로, T(n) = T(n/3) + T(5n/6) + Θ(n) ≤ 1/3cn + 5/6cn + Θ(n) = 7/6cn + Θ(n) > cn이 되어 가정이 틀렸음을 알 수 있다. 즉, 3개의 집단으로 나누면 Select 알고리즘의 큰 특성인 선형 성능을 잃는다는 결론을 얻는다.

여기서 만약 O(n²)으로 가정하면 T(n) = 1/9cn² + 25/36cn² + Θ(n) = 29/36cn² + Θ(n) < cn²으로 가정을 만족한다. 더 근접한 상계를 찾기 위해 이번엔 O(n·lg n)이라 가정하면 T(n) = cn/3(lg cn – lg 3) + 5cn/6(lg cn + lg5 – lg 6) + Θ(n) = 7cn/6(lg cn) – cn/6(2lg3 - 5lg5 + 5lg6) + Θ(n) = 7/6cn(lg cn) + cn/6(lg9 – lg25 + lg7776) + Θ(n) > 7/6cn(lg cn) + Θ(n) > cn(lg cn)이므로 가정에 모순이다.

따라서 1<k≤2인 O(n^k)을 만족한다고 가정한다. 그리고 k를 1.1에서 0.1씩 높이며 대입해 나가면 1.4(소수점 자리를 늘리면 1.3725 정도)에서 최초로 가정이 만족되므로 O(n^1.4)을 찾게 된다.