我試圖確定合併排序爲大澳的運行時間，運行時間：什麼是合併排序的這些輸入
（A）進行分類輸入
（B）反向有序輸入
（C）隨機輸入
我的答案是，它會採取所有三種情況爲O（n LGN），因爲不管輸入的默認順序的，歸併排序總是將輸入到最小1元素的單位。然後它會將每個元素與相鄰列表中的每個元素進行比較，以對兩個相鄰列表進行排序和合並。它將繼續這樣做直到最後所有的元素都被排序和合並。
也就是說，我們真正需要找到然後是一般歸併排序的大O的複雜性，因爲最差，平均和最好的情況下都會採取同樣的時間。
我的問題是，有人可以告訴我，如果我的答案是正確的，如果是的話，解釋爲什麼歸併排序的大O的複雜性最終是爲O（n LGN）？
此問題的答案取決於您對Merge Sort的實施。 當天真地實現時，合併排序確實使用O（n * log n）時間，因爲它總是將輸入分爲最小單位。但是，有一個特定的實現叫做Natural Merge Sort，如果它們已經在輸入數組中進行排序，那麼它們將保持數字的正確順序，基本上首先查看給定輸入並確定哪些部分需要排序，劃分，然後再合併。
自然歸併排序將只需要O（n）的時間爲有序的輸入和在一般更快比爲反向有序輸入的隨機輸入。在後兩種情況下，運行時將爲O（n * log n）。
要回答你最後的問題，我會看看「正常」Mergesort;這種解釋更容易。
請注意，Mergesort可以被視爲一個二叉樹，其中在根中我們有整個輸入，在下一個層上，你可以從輸入分割一次獲得兩個半部分，在第三個層上我們有四個四分之一等等...在最後一層，我們終於有個人號碼。
然後注意，整個樹是O（log n）的深（這也可以從數學上證明）。在每一層上，我們必須對n個數字進行一些比較和交換 - 這是因爲當我們沿着樹走時，圖層上的總數量不會減少。在圖片中，我們需要對每個圖層上的8個數字進行比較和互換。 Mergesort的工作方式，我們實際上必須做正好 8個比較和直到每層8次交換。如果我們有一個長度爲n的輸入而不是8，那麼我們需要進行n次比較，每層最多n次交換（這是O（n））。我們有O（log n）層，所以整個運行時間將是O（n * log n）。
如果數據被排序或反轉，則標準合併排序僅使用n/2比較每次通過。隨機數據需要更多的比較。對於隨機數據，合併單個數字需要n/2次比較。成對數字的最差情況合併需要3n/4比較。最壞的情況合併4個數字的集合需要7n/8比較。最壞的情況下，8,15n/16，...等等，隨着集合變大而趨於n。標準合併排序原始數據和臨時數組之間的移動次數總是相同的，n log（n）。 – rcgldr
自然歸併排序的變體也處理反序排列，在整個排列相反的特殊情況下也會花費O（n）時間。如果整個文件沒有排序（正向或反向），那麼日誌因子會增加，但它仍然是（n logx（n）），其中logx（n）是排序數據所需的遍數。 – rcgldr
有很多答案，以便回答您的疑問。另外，在所有情況下，您都完全正確，所花費的時間將類似。 – vish4071
大O的複雜性是O（n log（n）），因爲這是在原始數組和工作數組之間執行的移動次數。對於n個元素，有ceil [log2（n）]（上限被四捨五入），每次移動n個元素，總共有O（n log（n））個移動。隨機數據的比較次數少一點，對於有序數據或反向數據最好的情況是n/2log（n），但1/2因數是一個常數，所以總體複雜度保持爲O（nlog（n）） 。 – rcgldr