使用合并排序的字符串排序

排序的最差复杂度是什么n每个字符有n个字符？它会只是其平均值的n倍。案例O(n log n)还是别的...？使用合并排序的字符串排序

来源

2012-02-26 Abhishek

你在说什么？ – uday 2012-02-26 00:31:55

目前还不清楚你在问什么。 – 2012-02-26 00:32:05

编辑我的问题..... – Abhishek 2012-02-26 00:40:47

作为@orangeoctopus，使用n大小的字符串集合上的标准排名算法将导致O(n^2 * logn)计算。

但是请注意，您可以可以在O(n^2)中执行此操作，其变化范围为radix sort。

做[在我看来]最简单的办法 - 就是

建立trie，并与您的所有字符串填充它。进入每个字符串O(n)，你做n倍 - 共O(n^2)
做字典树上一个DFS，每次遇到大关结束字符串时 - 将其添加到收藏排序。以这种方式添加的字符串的顺序是按字典顺序排列的，因此当您完成后，您的列表将按字典顺序排序。

很容易看到你不能做任何更好然后O(n^2)，因为只有在读取数据是O(n^2)，因此这种解决方案的时间复杂度大O表示法方面最佳。

来源

2012-02-26 06:55:58 amit

我认为不是说“DFS”，而是说“预先遍历”会更清楚。 – CEGRD 2012-11-26 03:10:48

不需要使用trie也可以实现'O（n^2）'吗？ – Kshitij 2014-06-26 15:30:55

@Kshitij是的，对字符串进行基数排序，trie仅仅是一个建议 - 标准基数排序将在这里工作 - 每次迭代使用字符（或他们的位表示）来实现当前的部分顺序，直到您耗尽所有位/字符。这也需要'O（n^2）'。 – amit 2014-06-26 21:11:08

当您在谈论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)

来源

2012-02-26 00:34:52

你不是指“O（M）哪里M ...”而不是“O（N）哪里N ...”？虽然这是最糟糕的表现，但要求，应该注意的是，比较两个字符串的平均大小写性能是O（1），因为它几乎变得越来越少，您不需要访问字符串中的每个额外字符。 – xan 2012-02-26 01:28:39

当然，我的意思是他们是分开的，但我改变它使用'M'更清晰。他要求的是“最差的复杂度”，但是给出了“平均”的刺痛大小......所以它仍然是O（N），对吧？ – 2012-02-26 01:31:28

是的，这个问题有点不清楚，最糟糕的和平均的混合。我认为你的答案会更强大，涵盖两者。 – xan 2012-02-26 01:40:21

使用MergeSort排序n个项目需要O(N LogN)比较。如果比较两个项目的时间是O(1)那么总运行时间将是O(N logN)。但是，比较两个长度为N的字符串需要O(N)时间，所以一个天真的实现可能会停留在O(N*N logN)时间。

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

这是一个想法。创建一个Trie结构并在那里放置N个字符串。该特里将有O(N*N)节点并需要O(N*N)时间来构建。遍历树并在树上的每个节点上放置一个整数“排名”;如果R（N1）< R（N2），则与字节相关联的字符串在字典中与节点2相关联的字符串之前。

现在继续Mergesort，通过查找Trie在O(1)时间进行比较。总运行时间将为O(N*N + N*logN) = O(N*N)

编辑：我的回答非常类似于@amit。但是，我继续在构建步骤之后继续使用radixsort的mergesort。

来源

2012-02-26 09:11:13

您是否还将索引映射到trie节点以便您可以在合并排序期间访问这些排名？请澄清。另外，我认为你还应该包括遍历的代价。所以复杂度应该是O（N * N + N * N + N * logN）。如果这是真的，那么基数排序方法似乎更好，因为它是O（N * N + N * N）。 – CEGRD 2012-11-26 03:22:27

@CERGD：大O符号仅针对输入大小的渐近增长;它不处理常数因子O（2 * N * N + NlogN）= O（N * N）。几个月后重新审视这个问题，很明显，阿米特的答案更简单快捷。尽管如此，我不同意你的观点：衡量实际表现的唯一方法是使用计时表，而不是查看O符号中的常数因子。甚至有些情况下，在实际情况下具有较大O（）函数的算法会击败另一种算法。 – 2012-11-26 09:24:48

使用合并排序的字符串排序

回答

相关问题