algorithm - 使用合并排序对 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²)

等式中的 n 表示要排序的列表中的元素数。 O(n²) 并不完全正确。它是 O(n * n 个字符比较)。 如果我们用不同的复杂度替换“n 字符比较”操作，这将是显而易见的，这与元素的数量无关。 让它成为 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)

现在，用n代替m

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

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

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

希望对您有所帮助!