快速排序精確分割是n-1？

我「用」瞭解Quicksort，現在..我已經弄糊塗了。我知道我錯過了一些非常明顯的東西，毫無疑問，Quicksort是O(nlogn)，n部分很容易看到（因爲我們需要在每個級別上使用n比較來根據相應的元素移動元素，但是如何？拆分logn不該」這是n-1？例如：。快速排序精確分割是n-1？

       1, 2, 3, 4 
         1, 2    3, 4 
        1  2  3  4

我們在第一級分裂1, 2, 3, 4成1, 2和3, 4，這是一個分裂然後在我們分裂1, 2爲1 and 2和3, 4到3 and 4第二級，這是2分裂，所以總共3分裂，所以n-1分裂？

我不認爲這是重複的，因爲我假設快速排序算法的平等分割（或者相當於分而治之算法的通用平等分割）我所要求的是直觀解釋爲什麼分裂是log(n)儘管事實上，當你計算實際的拆分調用數量它是n-1在任何通用的劃分和征服alogirhtm

來源

2015-11-02 q.Then

可能的重複[直觀解釋爲什麼QuickSort是n日誌n？]（http://stackoverflow.com/questions/10425506/intuitive-explanation-for-why-quicksort-is-n-log-n） –

它也很好記，實際上，在最壞的情況下，quicksort實際上是O（n^2）。它被認爲是O（nlogn），如果樞軸選擇得很好/它在大部分時間平均爲nlogn –

好的，但我在我繪製的圖中假定有相同的分區（並且這是針對任何類型的分而治之算法）然而，加起來的分裂是n-1 –

好的，在評論中做了一些澄清之後，很明顯這裏提到了什麼。

查看拆分被調用的次數的錯誤，這實際上是非常不相關的。有關的是原始操作的總數。

如前所述，樹的深度大約是log N.在樹的每個「層」上，檢查輸入的所有元素（並且可以交換一些元素）。

是的，在頂層你做一次調用將數組分成兩部分，然後在下一層再將每一部分分成兩半，依此類推。在給定的水平上調用partition（或split，或者任何你喜歡稱之爲的）的數量並沒有真正改變任何東西。重要的是，每次分割一些數據時，都需要查看該分區中的每個數據項。在頂層，我們有一個調用分區的例子，看看整個數組。在下一級，我們有兩個調用，每個調用看一半數組。第三，我們有四個調用，每個調用都查看數組的四分之一（依此類推）。

請注意，不完美的分割不會改變我們需要在樹的每個級別查看的項目數量。在樹的每一層，我們需要查看所有分區中的所有項目。如果分裂不在中心，這意味着我們在樹中會有多於Log（N）層，但是在樹的每一層，我們仍然需要查看每個輸入項。

因此，基本操作的總數是輸入項的數量乘以樹中的層數（在完美分區的情況下大約爲N），從而給出總體複雜度O （N log N）。如果分裂是不完美的，我們仍然在樹的每一級查看N個項目，但是我們有更多的層次 - 可能達到N層（給出最壞情況的複雜度）。

來源

2015-11-03 00:16:58

「平等分裂」，你得到一個平衡的二叉樹。

您正在做n每次迭代比較（執行「拆分」）。

問題是你需要多少次迭代？看看你的圖 - 它正在形成一個平衡的二叉樹。平衡二叉樹有多大？

來源

2015-11-02 23:54:36 TheGreatContini

是的我得到的平衡樹的高度是log（n），但是分割函數被調用的實際次數不是log（n），它是3.我們只需要做n次比較每個級別，但我們調用分裂功能3次以創建樹，或者我錯了嗎？ –

我認爲傑裏回答了你的問題，見上面的回覆。 – TheGreatContini

快速排序精確分割是n-1？

回答

相關問題