使用合并排序对 n 个字符串进行排序

Question

一个包含 n 个字符串的列表，每个字符串的长度为 n，使用合并排序算法按字典顺序排序。此计算的最坏情况 运行 时间是?

我搜索了这个问题，到处都发现答案是：O(n²logn)。

而我的做法如下：
比较两个字符串需要 O(n) 次比较，因此每次合并将花费 O(n²) 时间。
因此，递归方程为：
T(n) = 2T(n/2) + O(n²)
因此，通过大师方法：
T(n) = O(n²).

不对的地方指正

Answer 1

我认为您O(n^2*lgn)的结论是正确的。如果您要处理一组 n 个数字，我们知道合并排序需要 O(nlgn)。这里的区别在于我们现在处理的是字符串，每个字符串都是 n 长。对合并排序算法的唯一影响是比较基本情况下的两个字符串。我们将不得不比较两个字符串，而不是对两个数字进行 O(1) 比较。在一般情况下，这是一个 O(n) 操作，因为我们可能必须遍历两个长度为 n 的字符串中的每一个。

Answer 2

你的分析和还原是正确的。但问题出在主定理递归方程的解释上。

T(n) = 2T(n/2) + O(n²)

等式中的 n 表示待排序列表中的 no.of 个元素。 O(n²) 并不完全正确。它是 O(n * n 个字符比较)。 如果我们用不同的复杂度替换 'n-character comparisons' 操作，这将是显而易见的，这与 no.of 元素无关。 让它成为 O(m)。 那么我们有

T(n) = 2T(n/2) + O(n * m)

我们有 a = 2、b = 2、c = 1 和 c = Log_ba（案例 2）

因此， T(n) = O(n * m * log n)

现在，将 m 替换为 n

T(n) = O(n² * log n)

我们也可以证明这一点——归并排序的递归树的高度为 Log(n)。 O(n²) 的工作将在合并操作中的递归树的每一层完成。

因此，总共 O (n² log n)

希望对您有所帮助！

Answer 3

arunk2 的回答是正确的，但这里有一些关于重复出错的确切位置的更多详细信息：

在正常的归并排序中，递归是：T(n) = 2T(n/2) + cn ；其中 c 是某个常数

注意求解这个递归时发生了什么，以及用 c(n^2)

求解递归 T'(n) 时的区别

T(n) = 2T(n/2) + cn

T(n) = 2[2T(n/(2^2)) + c(n/2)] + cn

T(n) = (2^2)T(n/(2^2)) + cn + cn //logn步后，'cn'会被加logn次，因此导致 O(nlogn)

---

T'(n) = 2T(n/2) + c(n^2)

T'(n) = 2[2T(n/(2^2)) + c((n/2)^2)] + c(n^2)

T'(n) = (2^2)T(n/(2^2)) + c(n^2)/2 + c(n^2) //每个时间 n^2 减半，结果为 O(n^2)

如果你仔细分析算法，（正如arun的回答中提到的那样），每一级完成的工作总是n^2，并且不会在每一级减半，这就是为什么时间复杂度是O((n^2)logn) 而不是简单的 O(n^2) 由大师定理。