合併排序的時間複雜度

爲什麼自頂向下合併排序的最佳情況的時間複雜度爲O（nlogn）？我認爲自上而下合併排序的最好情況是1，只需要比較1次。如何在最差的情況下自下而上合併排序的時間複雜度，最好的情況和平均情況。合併排序的時間複雜度

還有一個問題是爲什麼每次迭代只需要O（n）？有人可以幫忙嗎？

2012-10-12 Chwa

'O（1）'？也許'O（n）'通過預處理和檢查數組已經排序。 – amit

「最好的情況」意思是「假設輸入大小爲'n'的最佳情況」，而不是假定只有2個項目需要排序的最佳情況。 –

描述你的算法，你認爲它O（1），我們可以告訴你它錯在哪裏... – Chris

爲什麼自頂向下合併排序的最佳情況的時間複雜度爲 O（nlogn）？

因爲在每次迭代中，您將數組拆分爲兩個子列表，並遞歸調用算法。在最好的情況下，你將它精確地分成一半，因此你可以將問題（每次遞歸調用）減少到原始問題的一半。您需要log_2（n）次迭代，並且每次迭代的確切次數爲O(n)（每次迭代都在所有子列表上，總大小仍然爲n），因此總共爲O(nlogn)。

但是，通過簡單的預處理來檢查列表是否已經排序 - 它可以減少到O(n)。

由於檢查列表是否排序本身是O(n) - 它不能在O(1)中完成。請注意，「最佳情況」是一般n的「最佳情況」，而不是特定的大小。

如何在最差的情況下自下而上合併排序的時間複雜度最差的情況下，最好的情況下和平均情況。

同樣的方法可以給你O（n）最好的情況自下而上（簡單的預處理）。自下而上合併排序的最差情況和最佳情況是O(nlogn) - 因爲在這種方法中，列表總是被分成2個等長（至差1）列表。

來源

2012-10-12 10:33:22 amit

爲什麼迭代應該是log_2（n）？有沒有這方面的公式？還有一個問題是關於二叉樹，爲什麼二叉樹的長度是log（n）。 – Chwa

@Justin：在遞歸的最深層次上，你有1個元素。第二級你有2.第三級你有4，第四級你有8，....在第i級你有2 ^（i-1）元素。所以我們正在尋找'i'，使得'2 ^（i-1）= n'。因爲'2^logn == n'，所以我們得出結論'i = logn + 1' - 所以迭代的總數是'O（logn）'二元樹也是一樣的 – amit

你的意思是有1個元素，2個元素？你的意思是，起初，有一個數組列表，其次，它分爲兩部分，所以到目前爲止.. – Chwa

合併排序的時間複雜度

回答

相關問題