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

Question

如果要对 n 个字符串进行排序，每个字符串都有 n 个字符，那么最坏情况下的时间复杂度是多少？它只会是平均情况下的 O(n log n) 的 n 倍吗？还是其他什么情况…？

- Abhishek

---

你的问题不太清楚。 - Oliver Charlesworth

Answer 1

当您在讨论两个长度不同的事物的O符号时，通常希望使用不同的变量，例如M和N。

因此，如果您的归并排序是O(N log N)，其中N是字符串的数量...比较两个字符串是O(M)，其中M与字符串的长度成比例，那么您将得到：

O(N log N) * O(M)

或者

O(M N log N)

其中M是字符串长度，N是字符串数量。你想使用不同的标签，因为它们的含义不同。

在字符串平均长度随着字符串数量缩放的奇怪情况下，例如如果你有一个存储在字符串中的矩阵或类似的东西，你可以认为M = N，然后你将有O(N^2 log N)

- Donald Miner

---

难道你的意思不是“O(M) 其中 M…” 而不是 “O(N) 其中 N…” 吗？虽然这是最坏情况的性能，但是需要注意的是，比较两个字符串的平均情况性能为 O(1)，因为你需要访问字符串中的每个额外字符的可能性会几何级数地变小。 - xan

当然，我本意是将它们分开，但我改用 M 来使其更清晰。他要求“最坏复杂度”，但给出了“平均”字符串大小……所以它仍然是 O(N)，对吧？ - Donald Miner

是的，这个问题有点不清楚，因为它混合了最坏和平均的概念。我认为你的答案应该更全面地涵盖两者。 - xan

是的 - 通常我对答案付出的努力与问题所付出的努力成比例 :) - Donald Miner

但是现在我认为它只能达到O(n^2)。 - Abhishek

Answer 2

作为@orangeoctopus所说，对于一个大小为n的字符串集合使用标准排序算法会导致O(n^2 * logn)的计算量。

然而请注意，您可以使用基数排序的变体在O(n^2)内完成。

我认为最简单的方法是：

1.构建一个Trie，并将所有字符串填充到其中。输入每个字符串的时间复杂度为O(n)，总共需要进行n次 - 总时间复杂度为O(n^2)。

2.在Trie上进行DFS，每次遇到字符串结束标记时将其添加到已排序的集合中。这种方式添加的字符串顺序是按字典顺序排序的，因此完成后您的列表将按字典顺序排序。

很容易看出，你不能比O(n^2)更好地完成它，因为只读取数据就是O(n^2)，因此从时间复杂度的大O符号来看，这个解决方案是最优的。

- amit

---

我认为，与其说“DFS”，不如说“先序遍历”更清晰明了。 - CEGRD

不使用 trie 数据结构，能否实现 O(n^2) 的时间复杂度？ - Kshitij

@Kshitij 是的，在字符串上执行基数排序，字典树只是一个建议 - 在这里使用标准的基数排序将起作用 - 每次迭代使用字符（或其位表示）来实现当前部分顺序，直到耗尽所有位/字符。这也将需要 O(n^2) 的时间。 - amit

Answer 3

使用MergeSort对n个项目进行排序需要O（N LogN）比较。如果两个项目之间比较的时间为O（1），则总运行时间将为O（N logN）。但是，比较长度为N的两个字符串需要O（N）的时间，因此天真的实现可能会卡在O（N * N logN）时间。

这似乎很浪费，因为我们没有利用每次只有N个字符串进行比较的事实。我们可以以某种方式预处理字符串，以便平均而言比较所需的时间更少。

这里有一个主意。创建一个Trie结构并将N个字符串放入其中。Trie将具有O（N * N）个节点，并且需要O（N * N）的时间来构建。遍历树并向树上的每个节点放置整数“排名”；如果R（N1）＆lt; R（N2），则与Node1关联的字符串出现在与Node2关联的字符串之前的字典中。

现在继续进行Mergesort，在Trie中查找以O（1）的时间进行比较。总运行时间将为O（N * N + N * logN） = O（N * N）

编辑：我的答案与@amit非常相似。然而，在构建trie之后，我继续使用归并排序，而他则使用基数排序。

- Ali Ferhat

---

你是否也保留了将单词映射到 trie 节点的索引，以便在归并排序期间访问这些排名？请澄清一下。此外，我认为你还应该包括遍历的成本。因此，复杂度应该是 O(NN + NN + NlogN)。如果这是正确的，那么基数排序方法似乎更好，因为它是 O(NN + N*N)。 - CEGRD

@CERGD：大O符号仅涉及相对于输入大小的渐近增长，而不涉及常数因子，O(2NN + NlogN) = O(N*N)。几个月后重新审视这个问题，很明显amit的答案更简单、更快。尽管如此，我不同意你的观点：衡量实际性能的唯一方法是使用计时器，而不是查看O符号中的常数因子。甚至有些情况下，具有更大O()函数的算法在实际情况下会击败其他算法。 - Ali Ferhat