證明3路快速排序大O綁定

Question

對於3路快速排序（雙樞軸快速排序），我怎麼會去尋找大O綁定？任何人都可以告訴我如何派生它？

Answer 1

有之間的細微差別發現的算法的複雜性和證明它。

要找到了該算法的複雜性，可以作爲阿米特做對方的回答說：你知道，在平均，你拆你的尺寸n的問題分解成大小n/3的三個小問題，所以你將在平均èlog_3（n）「步驟中獲得大小爲1的問題。憑藉經驗，您將開始感受到這種方法，並能夠通過涉及到的子問題思考它們，從而推導出算法的複雜性。

到證明該算法在O(nlogn)運行的平均情況下，您使用Master Theorem。要使用它，你必須編寫遞歸公式，給出排序數組的時間。正如我們所說的，排序大小爲n的數組可以分解爲排序大小爲n/3的三個數組以及構建它們的時間。這可以寫成如下：

T(n) = 3T(n/3) + f(n) 

凡T(n)是一個功能，給予解決「時間」大小n（實際需要的基本操作的數量）的輸入，並f(n)給需要「時間」將問題分解爲子問題。

對於三維快速排序，f(n) = c*n，因爲您要經過數組，檢查每個項目的放置位置並最終進行交換。這使我們處於Case 2 of the Master Theorem，其中規定，如果f(n) = O(n^(log_b(a)) log^k(n))一些k >= 0（在我們的例子k = 0）然後

T(n) = O(n^(log_b(a)) log^(k+1)(n))) 

由於a = 3和b = 3（我們把這些從遞推關係，T(n) = aT(n/b)），簡化爲

T(n) = O(n log n) 

而這是一個證明。

Answer 2

那麼，同樣證明實際持有。

每次迭代拆分陣列分成3子列表，平均這些子列表的大小是n/3每個。
因此 - 所需的迭代次數是log_3(n)，因爲你需要找到你做(((n/3) /3) /3) ...的次數，直到你得到一個。這給你的公式：

n/(3^i) = 1 

這是滿意的i = log_3(n)。

每次迭代仍然會在所有的輸入（但在不同的子表） - 一樣的快速排序，它給你O(n*log_3(n))。

由於log_3(n) = log(n)/log(3) = log(n) * CONSTANT，你得到的運行時間是O(nlogn)平均。

請注意，即使您採用更悲觀的方法來計算子列表的大小，通過採用最小均勻分佈 - 它仍然會得到第一個大小爲1/4的子列表，第二個大小爲1/2的子列表，和最後一個大小爲1/4（最小和最大均勻分佈）的子列表，它將再次衰減到log_k(n)迭代（不同的k> 2） - 這將再次產生O(nlogn)。

---

正式，證明會是這樣的：
每次迭代花費最多c_1* n OPS運行，爲每個n>N_1，對於一些常數C_1，N_1。 （大O符號的定義，以及除迭代外每次迭代爲O(n)的說法，請說明爲什麼這是真的。請注意，在這裏 - 「迭代」是指算法在某個「級別」完成的所有迭代，而不是一個遞歸調用）。

如上所見，你有log_3(n) = log(n)/log(3)迭代的平均情況（以樂觀的版本，在這裏，可以用於悲觀相同的原則）

現在，我們得到了該算法的運行時間T(n)是：

for each n > N_1: 
T(n) <= c_1 * n * log(n)/log(3) 
T(n) <= c_1 * nlogn 

通過definition of big O notation，這意味着T(n)是在O(nlogn)與M = c_1和N = N_1。
QED