快速排序的複雜性

Question

所以我正在參加考試，而且這個考試的很大一部分將是快速排序算法。衆所周知，最好的情況下，該算法的實際平均情況是：O(nlogn)。最壞的情況是O(n^2)。

至於最壞的情況下，我知道該怎麼解釋呢：它發生時，所選擇的支點將是最小的或數組中的最大價值，那麼我們將有可能需要長達n時間n快速排序呼叫（我的意思是分區操作）。我對嗎？

現在是最好的/平均情況。我讀過科爾門書，由於那本書我懂得很多東西，但至於快速排序算法，他專注於關於如何解釋O(nlogn)複雜性的數學公式。我只是想知道爲什麼它是O(nlogn)，沒有進入一些數學證明。現在我只看到一些維基百科的解釋，如果我們選擇一個每次將我們的數組分成n/2, n/2+1部分的數據透視表，那麼我們將有一個深度爲logn的調用樹，但我不知道這是否是真的，甚至是如果是這樣，那爲什麼logn呢。

我知道互聯網上有很多涵蓋快速排序的材料，但它們只涵蓋實現，或者只是告訴我複雜性，而不是解釋它。

Answer 1

對嗎？

是的。

我們將不得不深入logn的調用樹，但我不知道這是否是真的

它。

爲什麼是logn？

因爲我們在每一步將數組劃分爲一半，導致調用圖的深度爲logn。從這個Intro：

看樹和它的深度，這是logn。想象一下，在BST中搜索的代價爲logn，或者爲什麼在排序數組中的二進制搜索中搜索也需要logn。 PS：數學說實話，投資理解它們，你會成爲一個更好的計算機科學家！ =）

Answer 2

對於最好的情況，快速排序在每個分區步驟上將當前數組的50％/ 50％（一半）拆分爲O（log2（n））（1/.5 = 2 ），但是常數2被忽略，所以它是O（n log（n）

如果每個分區步驟產生20％/ 80％的分裂，那麼最壞情況的時間複雜度將基於80％或O（n log1.25（n））（1/.8 = 1.25），但常數1.25被忽略，所以它也是O（n log（n）），即使它比50％/ 50慢大約3倍用於排序100萬個元素的％分區情況。

當分區分割僅在每個分區步驟中產生分區大小的線性縮減時，會發生O（n^2）時間複雜度。最簡單和最差的情況是每個分區步驟僅刪除1個元素。