什么是Array.prototype.sort()时间复杂度? [英] What is Array.prototype.sort() time complexity?

问题描述

根据Mozilla文档:

不能保证排序的时间和空间复杂性，因为它取决于实现方式.

至少可以安全地假设它不是 O(n ^ 2)吗?是否存在有关其实施方式的更详细的数据?谢谢.

解决方案

Firefox使用 Timsort 的合并排序和插入排序的混合版本..>

合并排序的时间复杂度为 O(n log n).尽管规范未指定要使用的排序算法，但在任何严重的环境中，您可能会希望对较大的数组进行排序所花费的时间不会长于 O(n log n)(因为如果这样做了，可以很容易地更改为更快的算法，例如合并排序或其他一些对数线性方法).

虽然比较排序(例如合并排序)有一个 O(n log n)的下限(即，至少要花这么长时间才能完成)，Timsort利用了运行"已排序数据的优势，因此下限为 O(n).

According to Mozilla documentation :

The time and space complexity of the sort cannot be guaranteed as it depends on the implementation.

Is it at least safe to assume that it's not O(n^2)? Is there anywhere more detailed data about how it's implemented ? Thanks.

解决方案

Firefox uses merge sort. Chrome, as of version 70, uses a hybrid of merge sort and insertion sort called Timsort.

The time complexity of merge sort is O(n log n). While the specification does not specify the sorting algorithm to use, in any serious environment, you can probably expect that sorting larger arrays does not take longer than O(n log n) (because if it did, it would be easy to change to a much faster algorithm like merge sort, or some other log-linear method).

While comparison sorts like merge sort have a lower bound of O(n log n) (i.e. they take at least this long to complete), Timsort takes advantages of "runs" of already ordered data and so has a lower bound of O(n).

这篇关于什么是Array.prototype.sort()时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！