84669 person learning
152542 person learning
20005 person learning
5487 person learning
7821 person learning
359900 person learning
3350 person learning
180660 person learning
48569 person learning
18603 person learning
40936 person learning
1549 person learning
1183 person learning
32909 person learning
认证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)
你自己写个插排、快排,然后自己测量下时间不就知道了。
要么你自己写个标准的插排,再把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)
大。