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

Question

使用归并排序算法将长度为n的n个字符串按字典顺序排序。这个计算的最坏运行时间是什么？

我搜索了这个问题，无论在哪里，都发现答案是O(n^2logn)。

而我的方法如下： 比较两个字符串需要O(n)次比较，因此每次合并需要O(n^2)的时间。 因此，递归方程式为： T(n) = 2T(n/2) + O(n^2) 因此，通过主方法： T(n) = O(n^2)。

请在我有错误的地方纠正我。

- Rishabh Gupta

Answer 1

您的分析和约减是正确的。但问题在于主定理中递归方程的解释。

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

方程中的n代表要排序的列表中的元素数量。O(n²)不完全正确。它是O(n * n个字符比较)。如果我们用与元素数量无关的不同复杂度（假设为O(m)）替换“n个字符比较”的操作，这一点将变得明显。

因此，我们有

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

其中a=2，b=2，c=1，且c = Log_ba (第二种情况)。

因此，

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

现在，用n替换m，我们得到

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

我们也可以证明这一点：归并排序的递归树高度为Log(n)。在合并操作的每个递归树层级上，都会执行O(n²)的工作。

因此，总的时间复杂度是O(n² log n)。

希望能对您有所帮助！

- arunk2

Answer 2

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

- Tim Biegeleisen

---

每个字符串是O(nlgn)是什么意思？ - meowgoesthedog

@meowgoesthedog 狗真的会喵喵叫吗？ - Tim Biegeleisen

我的问题的答案真的那么明显吗？我不认为 OP 的意思是要在字符串内部进行排序。 - meowgoesthedog

我对问题的理解是，我们有n个字符串，每个字符串的字符都必须进行排序。由于每个字符串都有n个字符，因此通过归并排序进行排序将是一个O(nlgn)的操作，对于所有n个字符串则为O(n^2*lgn)。但问题还有第二部分，即对这n个单词进行排序。这同样是一个O(nlgn)的操作；但它不会改变总运行时间。但也许我在这里是错的。 - Tim Biegeleisen

我认为OP的意思是按照字典顺序排序字符串（因此是词典顺序）。 - meowgoesthedog

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)，根据主定理。

- Rishabh Gupta