これは、私のデータ構造の宿題に関する質問の 1 つです。
配列の少なくとも 1% がピボット以下であり、少なくとも 1% がピボット以上であるような Quicksort のピボット要素を見つけることが保証されている線形時間手順があるとします。クイックソートが最悪の場合の複雑さ O(n lg n) を持つことを示します。
一般的に、クイックソートの最悪の場合の複雑さは O(n^2) であることを知っています。これは、選択されたピボットのすべての値が取得されたセットの最大または最小のいずれかである場合に発生することを読みました。
私の推測では、配列の少なくとも 1% がピボットよりも大きく、配列の少なくとも 1% がピボットよりも小さいという特定の条件のため、これにより、ピボットがセット内の最小または最大の要素である状況が解消されます。 . したがって、O(n^2) になることはありません。
この音は正しいですか？
このタイプの問題の主な決め手は、O(log(n)) ステップしかないことを示していることです。
理想的なクイックソート再帰は
T(N) = 2T(N/2) + O(n)
これはマスター定理によって O(NlogN) であることを簡単に示すことができます。
O(n) 項は、再帰ツリーのすべてのレベルの要素です。さらに、理想的なケースでは、すべての要素をすべてのレベルで処理する必要があります。技術的には、ほとんどの要素が他の要素よりも再帰ツリーのはるか下にある場合でも、「最悪のシナリオ」が発生し、すべての要素がすべてのレベルで処理されることを漸近損失なしで想定できます。したがって、与えられた仮定の下で再帰ツリーに最大で O(log(N)) ステップがあることを証明する必要があります。
あなたの仮定を前提としたクイックソート再帰：
T(N) = T(N/100) + T(99N/100) + O(n).
WLOG では、再帰ツリーの 1 つの分岐に 99 個以下の要素があると、それらを並べ替えるために最大で一定数の操作のみが発生すると想定できます (したがって、O(1) * O(n) = O(n ) 最下位レベルで発生する操作; 再帰ツリーは縮小も拡大もしません)。
では、ツリー全体の最大ステップ数をどのように証明すればよいでしょうか? さて、私たちは最も不運な要素に従います! N 個の要素から始めるとします。私たちの仮定を考えると、実際に関心のある再帰ツリーのレベルの最終ステップの最大の分岐を形成する要素は 50 から 99 の間のどこかにあるはずです。彼らがこれまでに受けた最悪の操作は、すべて 99% の一部です。
したがって、1% カットされる X 回の反復によって形成される要素は、最大で 99 個です。これは、以前に見たはずの別の再帰ツリー、つまり「幾何学的に減少する」ツリーのように見えるはずです。数学に関しては：
99 = N*(.99)^X
99/N = (1/.99)^-X
(1/.99)^X = N/99
log_(1/.99) (1/.99)^X = log_(1/.99) N/99
X = log_(1/.99) N/99
ご覧のとおり、右側の項は O(log(N)) です。したがって、これは再帰のレベルの最大数であり、それぞれが最大で O(N) の作業を行うため、合計の作業は O(Nlog(N)) です。
それ以上の厳密さが必要かどうかはわかりませんが (実際の再帰証明を最初から説明するのは大変な作業です)、ほとんどの大学ではこれで問題ありません....