17101181_강병선_분할정복알고리즘_연습문제
개정판
배열에 있는 숫자들에 대해서 합병 정렬이 수행되는 과정을 보이라.
퀵 정렬 알고리즘의 피봇이 랜덤하게 정해진다는 가정하에 퀵 정렬 알고리즘의 평균 경우 시간복잡도가 O(nlog2n)임을 보여라.
우선 element에 중복이 없다고 가정한다.
n의 리스트를 정렬하는데 걸리는 시간을 T(n)이라고 하자.
pivot과 항목을 비교하는 횟수는 n-1번.
즉 partition 시에 n-i-1, i의 사이즈를 가지게 된다.
이에 따르면 T(n)을 다음과 같이 표현할 수 있다.
$T(n) = n-1 + 1/n(\sum^{n-1}_{i=0}(T(i) + T(n-i-1))$ ...(1)
$= n-1+2/n\\sum^{n-1}_{i=0}T(i)$
$nT(n) = n(n-1) + 2\sum^{n-1}_{i=0}T(i)$
(1)에 의해 $T(n-1)= n-2+2/(n-1)\sum^{n-2}_{i=0}T(i)$ 이므로
$nT(n) - (n-1)T(n-1) = n(n-1) - (n-1)(n-2) + 2T(n-1)$
$\therefore nT(n) = (n+1)T(n-1) + 2n-2$
${T(n)} /{(n+1)} = T(n-1)/n + 2/(n+1) - 2/n(n+1)$
≤ $T(n-1)/n + 2/(n+1)$
$= T(n-2)/(n-1) + 2/n - 2/(n-1)n + 2/(n+1)$
≤ $T(n-2)/(n-1) +2/n + 2/(n+1)$
...
= $T(1)/2 + \\sum^{n}_{i=0} 2/(i+1)$
$≤ 2 \\sum^{n-1}_{i=0} 2/i$
$\approx 2 \int^n_1 1/x dx = 2 ln n$
$T(n) = 2n ln n \approx 1.39nlog_{2}n$