如果split是5：n-5，那麼時間複雜度會是多少？

Question

當分區大小之比爲5：n-5或類似於1:19的東西時，你如何發現快速排序的複雜性？我不太瞭解如何在這些情況下計算算法的複雜性。

Answer 1

一般來說，記住以下：

• 如果拆分的陣列到由一些固定的比率定義的兩個部分：b。在每個點，O-後（log n）的分裂，所述子陣列將下降到大小爲0

• 如果拆分的陣列分成兩片，其中一個的大小是一個常數k，將採取Θ（N/K）分割來獲得子陣列的尺寸下降至0。

現在，考慮一下quicksort在遞歸的每個級別所做的工作。在每一層，它需要按照圖層中元素的數量進行工作。如果你使用第一種方法，並且像1/20：19/20分割那樣，那麼每層最多隻有n個元素，但只有O（log n）層，因此所做的總工作將是O（n log n），這很好。

另一方面，假設您總是拉出五個元素。那麼每個步驟中的較大陣列將具有n，n - 5，n - 10，n - 15，...，10，5，0的大小。如果您計算出數學並對其進行求和，則可得出結果爲Θ （n ）全部工作，這不是非常有效。

一般來說，儘量避免在快速排序中一次拆分固定數量的元素。這給了你需要擔心的退化情況。