扫码关注官方订阅号
认证0级讲师
你自己写个插排、快排，然后自己测量下时间不就知道了。要么你自己写个标准的插排，再把v8里面用的那个插排弄出来，比较下代码，再测量下时间呗。
快排的时间平均时间复杂度是cNlog(N)，最坏情况下N^2/2,空间复杂度O(log(N))。c是一个常数,经验得出来的一个值。插入排序平均时间复杂度N^2/4，最坏N^2/2,空间复杂度O(1)。(上述公式也忽略了一下常数项和N的一次项，因为不是固定的)
cNlog(N)
N^2/2
O(log(N))
N^2/4
O(1)
所以 N 比较小(v8里给的是10)的时候 N^2/4不见得比 cNlog(N)大，比如设 N<=10,对数的底数取10，c=2.5的时候。另外同样是一步运算，插入排序只需要比较，交换;而快排需要比较，交换，平均下来的一点儿空间分配。 所以 N 比较小的时候不见得插入排序是慢的。
当 N 比较大的时候上面那些常数的影响可以忽略不计，那么N^2显然是比Nlog(N)大。
N^2
Nlog(N)
微信扫码关注PHP中文网服务号
QQ扫码加入技术交流群
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
PHP学习
技术支持
返回顶部
0 
2
809
收藏
你自己写个插排、快排，然后自己测量下时间不就知道了。
要么你自己写个标准的插排，再把v8里面用的那个插排弄出来，比较下代码，再测量下时间呗。
快排的时间平均时间复杂度是
cNlog(N)，最坏情况下N^2/2,空间复杂度O(log(N))。c是一个常数,经验得出来的一个值。插入排序平均时间复杂度
N^2/4，最坏N^2/2,空间复杂度O(1)。(上述公式也忽略了一下常数项和N的一次项，因为不是固定的)
所以 N 比较小(v8里给的是10)的时候
N^2/4不见得比cNlog(N)大，比如设 N<=10,对数的底数取10，c=2.5的时候。另外同样是一步运算，插入排序只需要比较，交换;而快排需要比较，交换，平均下来的一点儿空间分配。 所以 N 比较小的时候不见得插入排序是慢的。
当 N 比较大的时候上面那些常数的影响可以忽略不计，那么
N^2显然是比Nlog(N)大。