为什么要排序字符串O(n log n)？

Question

可能重复:
Big O的简单英文解释

在编程难题的答案中,它表示对字符串进行排序需要O(n log n)时间.这是怎么衍生出来的？

是否有人为Big O资源提供了良好的参考链接.

谢谢

Answer 1

为什么要排序字符串O(n log n)？

对字符串中的字符进行排序不一定是O(n log n).

• O(n log n)是比较排序的最佳值.它也是许多语言的默认排序实现的复杂性.然而,这肯定比这更糟糕.排序字符串中字符的复杂性取决于您选择用于解决此任务的特定算法.
• 在某些情况下,通过使用不是比较排序的排序算法,也可以比O(n log n)做得更好.例如,如果您知道您的ASCII字符串最多包含127个不同的字符,则可以使用计数排序,即O(n).对于所有字符都在Basic Multilingual Plane中的Unicode字符串,计数排序也是可行的.

Answer 2

Big O 的定义和一些例子可以通过使用搜索引擎找到，例如这里：

• http://en.wikipedia.org/wiki/Big_O_notation

可以在此处找到基于比较元素的排序算法的说明，以及所需比较次数下限的说明：

• http://en.wikipedia.org/wiki/Comparison_sort