クイックソートの奥行き複雑度

Question

私は試験を受けており、この試験の大きな部分はクイックソートアルゴリズムになります。誰もが知っているように、最良のケースのシナリオであり、実際にはこのアルゴリズムの平均ケースはO(nlogn)です。最悪のシナリオはO(n^2)です。

私はそれを説明する方法を知っています：選択されたピボットが配列の最小値または最大値になると、nクイックソートコールが発生し、n時間（私はパーティション操作を意味する）。私は正しい？

ここでは最高/平均の場合です。私はCormensの本を読んだので、その本のおかげで多くのことを理解しましたが、クイックソートアルゴリズムに関しては、O(nlogn)の複雑さを説明する数式に焦点を当てています。私はちょうどなぜそれがO(nlogn)であるかを知りたがっていて、数学的な証明にはならなかった。今のところ、Wikipediaの説明だけを見てきました。私たちの配列を毎回n/2, n/2+1の部分に分割するピボットを選択すると、深度がlognの呼び出しツリーがありますが、それが真であるかどうかわかりませんもしそうなら、それはなぜlognですか？

インターネット上にクイックソートをカバーする多くの資料があることは知っていますが、実装のみをカバーしているだけで、説明していない複雑さだけを伝えています。

Answer 1

私は正しいですか？

はい。

我々は深さlognのコールツリーを持っているだろうが、それはそれは真

ある場合、私は知りません。

なぜそれがlognですか？

私たちはすべてのステップで配列を半分に分割するので、コールグラフの深さはlognになります。このIntroから：

ツリーとその深さを参照してください、それはlognです。 BSTの検索でlognの検索が行われた場合、またはソートされた配列でバイナリ検索でlognが検索される理由を想像してください。

---

PS：数学は真実を伝え、それらを理解するために投資し、あなたはより良いコンピュータ科学者になろう！ =）

Answer 2

クイックソートは、O（log2（n））（1/0.5 = 2）の時間複雑度に対して、各パーティションステップで現在の配列を50％/ 50％

各パーティションステップが20％/ 80％スプリットを生成した場合、最悪の場合の時間複雑度は80％または80％に基づいています。 O（n log1.25（n））（1/.8 = 1.25）ですが、定数1.25は無視されるので、50％/ 50より約3倍遅くてもO（n log 100万の要素をソートするための分割ケース％。

O（n^2）時間の複雑さは、パーティション分割で各パーティションステップでパーティションサイズが直線的に縮小される場合に発生します。最も単純で最悪の例は、パーティションステップごとに1つの要素だけが削除された場合です。