Possible Duplicate:
Plain English explanation of Big O
In the answer to a programming puzzle it said sorting a string takes O(n log n) time. How is that derived?
Does anybody have a good reference link for Big O resources.
Thanks
Why is sorting a string O(n log n)?
Sorting the characters in a string is not necessarily O(n log 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.
A definition and some examples of Big O can be found by using a search engine, eg here:
http://en.wikipedia.org/wiki/Big_O_notation An explanation of sort algorithms based on comparing elements, together with an explanation for the lower bound on the number of required comparisons, can be found here:
http://en.wikipedia.org/wiki/Comparison_sort
链接地址:
http://www.djcxy.com/p/6750.html
上一篇:
什么是大O符号？
下一篇:
为什么排序字符串O（n log n）？
