为什么排序字符串O（n log n）？

 

可能重复：
Big O的纯英文解释

在编程难题的答案中，它表示排序字符串需要O（n log n）时间。 这是如何派生的？

有没有人有一个很好的大O资源的参考链接。

谢谢

为什么排序字符串O（n log n）？

排序字符串中的字符不一定是O（n log n）。

  • O（n log n）是比较排序的最佳值。 这也是许多语言默认排序实现的复杂性。 然而，当然可以做得比这更糟糕。 排序字符串中字符的复杂程度取决于您选择解决此任务的特定算法。
  • 在某些情况下，通过使用不是比较排序的排序算法，也可能比O（n log n）做得更好。 例如，如果您知道您拥有最多127个不同字符的ASCII字符串，则可以使用O（n）的计数排序。 对于所有字符都在基本多语言平面中的Unicode字符串，计数排序也是可行的。

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

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

    • 可以在这里找到基于比较元素的排序算法的解释以及所需比较次数的下限解释：

  • http://en.wikipedia.org/wiki/Comparison_sort
    • 链接地址: http://www.djcxy.com/p/6749.html

    上一篇: Why is sorting a string O(n log n)?

    下一篇: calculating time complexity of a algorithm