- 17 名前：デフォルトの名無しさん mailto:sage [2013/03/22(金) 10:45:09.98 .net]
- >>14
厳密な証明じゃないけど、入力(ソートする配列)のサイズを n として、パーティションのステップで n 、結果としてサイズ n/2 の配列が2つできる。2つのサイズ n/2 の配列に対してそれぞれクイックソートするから、合わせると
T(n) = n + 2T(n/2)
= n + 2{ n/2 + 2T(n/4) } = 2n + 4T(n/4)
= 2n + 4{ n/4 + 2T(n/8) } = 3n + 8T(n/8)
...
// 繰り返すと以下のようなパターンが見えてくる
...
= kn + 2^k * T(n / (2^k)) --------- (*)
になる。
T(n/(2^k)) の n / (2^k) が 1 になるとき、n = 2^k <---> k = log n
k = log n を (*) の式に戻してやると
= kn + 2^k * T(n / (2^k))
= n log n + n * T(1)
= O (n log n)
|
 |
