Analysis of Quicksort
재귀식은 아래와 같다.
T(n) = T(i) + T(n-i-1) + n
// 1, 2, ..., i, i+1(pivot), i+2, ..., n-1, n
// 즉, 좌집합 T(i), 우집합 (n-i-1)에 대한 Conquer 진행.
// 뒤의 n은 combine과정이 아니라 Partition cost를 의미한다.따라서, Worst case는 피봇 기준 어느 한 쪽으로 계속 치우쳐지는 경우로,
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
...
= T(1) + 2 + 3 + ... + (n-1) + n
= T(1) + (n+2)*(n-1)/2
= O(n^2)반면, Best case는 피봇 기준 항상 n/2로 나눠지는 경우로,
T(n) = 2*T(n/2) + n
Master method에 의해 n^log2(2) = n이 f(n) = n과 같으므로
Theta(nlog(n)).정리하기보단 직접 풀면서 공부하는 게 훨씬 효율이 좋은 듯 하여 여기까지만 기록하기로.
