驗證一次排序N個整數的複雜度，M一次

Question

我只問複雜度只有第一部分（排序部分）的一個更大的問題，稱爲外部排序。 N - 整數（適合內存的大整數） M - 可以使用歸併排序在內存中排序的整數數量。

複雜合併排序： O（M登入）

但是，我們需要理清全氮元素。因此，我們需要完全排序N/M次。 從而

O（（N/M）* M數M）

從而最終獲得

O（N日誌M）

這是正確的複雜性？如果不能糾正我的計算。

Answer 1

是的，這是一次對N個整數M進行排序的第一階段的正確複雜度。如果您說M大小的集合的數量是k，您可以以不同的方式表示相同的數字。那麼你可以說它是

O(N*Log(N/k)) 

Answer 2

如果你想最終排序所有N個元素，這是不夠的。您將您的總數N個數字分成N個M個子集中的每個M個數字。然後你排序每個子集。正如您正確地發現的那樣，這具有O（N log M）的複雜性，並且如果您的目標是結束一對已分類的子集，那麼您已完成並且一切都很好。然而，在這一點上，你沒有整套N分類，你只是有一些分類的子集，還有一些工作要做。還有什麼是將這些子集合並在一起的操作。假設您的合併操作始終將兩個子集合併爲一個，那麼您仍然有Log2（N/M）合併操作要做，每個操作的複雜度都是O（N）。所以最終的複雜度是O（N log M + N Log（N/M））= O（N Log N）。它應該是。