使用合并排序对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的字符串。