使用合併排序對n個字符串進行排序

Question

使用合併排序算法將每個長度爲n的n個字符串列表按字典順序排序。這種計算的最壞情況下運行時間是？

我搜索了這個問題，到處都找到了答案：O（n logn）。

雖然我的方法如下：
比較兩個字符串需要O（n）的比較，因此每個合併將採取爲O（n ）時間。
所以，遞推方程將是：
T（N）= 2T（N/2）+ O（N ）
因此，通過主方法：
T（N）= O（N ）。

糾正我錯在哪裏。

Answer 1

您的分析和減少是正確的。但問題在於對主定理的遞推方程的解釋。

T（N）= 2T（N/2）+ O（N 2 ）

公式中的n表示節數列表中的元素進行排序。 O（n ）並不完全正確。它是O（n * n個字符比較）。 如果我們用不同元素替代複雜度不同的'n字符比較'操作，這是顯而易見的。 設爲O（m）。 然後我們有

T（N）= 2T（N/2）+ O（n * m個）

我們有= 2，B = 2，C = 1和c =日誌 _b一個（情況2）

因此， T（N）= O（N * M * log n）的現在

，其中n代米

T（N）= O（N * log n）

我們也可以證明這一點 - 合併排序的遞歸樹將具有高度Log（n）。 O（n ）將在合併操作中的重複樹的每一級完成工作。

因此，總的爲O（n log n）的

希望它能幫助！

Answer 2

我認爲你的結論O(n^2*lgn)是正確的。如果您正在處理一組n數字，我們知道mergesort需要O(nlgn)。這裏的區別在於我們現在正在處理字符串，每個字符串長度爲n。對mergesort算法的唯一影響是基本情況下兩個字符串的比較。而不是兩個數字的比較，我們將不得不比較這兩個字符串。在一般情況下，這是一個O(n)操作，因爲我們可能不得不走下兩個長度爲n的字符串。