可能是重复问题：
Big O的简明英文解释
在一个编程谜题的答案中，它说“对一个字符串进行排序需要O(n log n)的时间”。这是怎么推导出来的？
有没有关于Big O资源的好参考链接？
有没有关于Big O资源的好参考链接？
2个回答
25
为什么对字符串进行排序的时间复杂度是O(n log n)？
对字符串中的字符进行排序并不一定是O(n log n)。
O(n log n)是比较排序的最优值。它也是许多语言默认排序实现的复杂度。然而，肯定有比这更差的情况。对字符串中的字符进行排序的复杂度取决于您选择的解决此任务的具体算法。
在某些情况下，可以通过使用非比较排序算法来获得比O(n log n)更好的性能。例如，如果您知道字符串是ASCII字符串，最多有127个不同的字符，您可以使用计数排序，其时间复杂度为O(n)。对于所有字符都在基本多语言平面的Unicode字符串，计数排序也是可行的。
对字符串中的字符进行排序并不一定是O(n log n)。
O(n log n)是比较排序的最优值。它也是许多语言默认排序实现的复杂度。然而，肯定有比这更差的情况。对字符串中的字符进行排序的复杂度取决于您选择的解决此任务的具体算法。
在某些情况下，可以通过使用非比较排序算法来获得比O(n log n)更好的性能。例如，如果您知道字符串是ASCII字符串，最多有127个不同的字符，您可以使用计数排序，其时间复杂度为O(n)。对于所有字符都在基本多语言平面的Unicode字符串，计数排序也是可行的。
- Mark Byers
0
可以通过搜索引擎找到关于Big O的定义和一些例子，例如在这里：
关于基于比较元素的排序算法的解释，以及所需比较次数下限的解释，可以在这里找到：
- Christian Semrau
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 6 二分查找的时间复杂度是O(log n)还是O(n log n)？
- 11 O(n log log n) 时间复杂度
- 3 这个算法的时间复杂度是O(log log n)吗？
- 66 为什么快速排序的时间复杂度是n log n？直观解释。
- 3 复杂度 O(log(n) + log(n/2) + log(n/4) + log(n/8) + ... + log(2)) 是否等于 O(log(n))？
- 6 计数归并排序包括对1、2、...、n的三个排列进行排序，时间复杂度为O(n log n)。
- 5 在O(n log(log n))时间复杂度内对数组进行排序。
- 3 时间复杂度如O(n/log n)、O(n^2/log n)在实践中很少见吗？
- 6 C++中的稳定划分 - 为什么时间复杂度是O(n log n)？
- 4 我对 n*log(N) 的时间复杂度 Big O 很感兴趣。