Q

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

2010-12-13 69 views 7 likes

7

可能重复：
Plain English explanation of Big O 为什么排序字符串O（n log n）？

在回答一个编程的难题故称排序字符串需要为O（n log n）的时间。这是如何派生的？

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

由于

2010-12-13 Percy Flarge

+0

你是什么意思'排序字符串'？你的意思是排序字符串列表吗？ – jjnguy 2010-12-13 22:06:27

+0

或者可能排序字符串中的字符.. – 2010-12-13 22:07:25

+1

它在字符串中排序字符。我知道什么是大O，我不知道为什么排序字符串中的字符是n log n。 – 2010-12-13 22:32:20

A

回答

1

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

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

的基于比较元件排序算法的说明，具有用于下限所需的比较的数量的说明一起，可以在这里找到：

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

2010-12-13 22:06:38

10

为什么要对字符串O（n log n）进行排序？

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

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

2010-12-13 22:13:12

相关问题