隨機化快速排序選擇25％-75％的樞軸選擇

我知道，如果我們選擇樞軸的方式至少會在配給率25％的情況下進行隨機化快速排序， 75％，那麼運行時間是O(n log n)。現在我也知道我們可以用主定理證明這一點。隨機化快速排序選擇25％-75％的樞軸選擇

但我的問題是，如果我們在每個步驟中將數組拆分爲25％-75％，那麼我將如何定義我的T(n)以及如何證明O(n log n)中的運行時分析？

2013-07-22 Sudipta Deb

您可以使用Master theorem來查找這類算法的複雜性。在這種特殊情況下，假設當將數組分成兩部分時，這些部分中的每一部分都不大於初始數組的3/4。然後，T(n) < 2 * T(3/4 * n) + O(n)或T(n) = 2 * T(3/4 * n) + O(n)如果您尋找上限。主定理給你這個方程的解決方案。

更新：雖然主定理可以解決這樣的遞推方程，在這種情況下，它給我們一個比預期的O（n * log n）更差的結果。儘管如此，它可以通過其他方式解決。如果我們假設一個支點總是以小於1/4的大小來分割數組，那麼我們可以將遞歸深度限制爲log_ {4/3} N（因爲在每個級別上，數組的大小都會減小至少4/3次）。每個遞歸級別的時間複雜度總共爲O（n），因此我們有O（n）* log {4/3} n = O（n * log n）的整體複雜度。此外，如果你想要一些更嚴格的分析，你可以考慮一篇Wikipedia文章，這裏有一些很好的證明。

來源

2013-07-22 19:05:19

嗨伊萬，謝謝你的迴應。但根據T（n）<2 * T（3/4 * n）+ O（n），值爲a = 2，b = 4/3，d = 1。所以它意味着一個> b^d。所以T（n）= O（n^log a [base b]）。但T（n）應該是O（nlogn）。你能告訴我我怎麼能證明這一點？謝謝 –

@SudiptaDeb哎呀，對不起，我已經忘記了一些主定理。這是一個更新的解決方案。 –

感謝您的澄清 –

隨機化快速排序選擇25％-75％的樞軸選擇

回答

相關問題