为什么要对字符串O（n log n）进行排序？ [英] Why is sorting a string O(n log n)?

问题描述

可能重复：

大O的简单英语解释

回答编程难题的原因是，对字符串进行排序需要O（n log n）时间。
它是如何得出的？

In the answer to a programming puzzle it said sorting a string takes O(n log n) time. How is that derived?

有人对Big O资源有很好的参考链接。

Does anybody have a good reference link for Big O resources.

谢谢

推荐答案

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

Why is sorting a string O(n log n)?

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

Sorting the characters in a string is not necessarily O(n log n).

• O（n log n）是最优值。 >比较排序。这也是许多语言默认排序实现的复杂性。但是，当然可以做得比这更糟。对字符串中的字符进行排序的复杂程度取决于您选择用于解决此任务的特定算法。


• 在某些情况下，通过使用O（n log n）也可能会做得更好不是比较排序的排序算法。例如，如果您知道ASCII字符串最多包含127个不同的字符，则可以使用计数排序为O（n）。对于所有字符都在基本多语言平面。

• O(n log n) is the optimal value for a comparison sort. It is also the complexity of many languages' default sort implementation. However it's certainly possible to do worse than this. The complexity of sorting the characters in a string depends on the specific algorithm you choose to solve this task.
• It's also possible to do better than O(n log n) in some cases by using a sorting algorithm which is not a comparison sort. For example, if you know that you have an ASCII string with a maximum of 127 distinct characters you could use a counting sort which is O(n). A counting sort would also be feasible for Unicode strings where all characters are in in the Basic Multilingual Plane.

这篇关于为什么要对字符串O（n log n）进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！