84669인 학습
152542인 학습
20005인 학습
5487인 학습
7821인 학습
359900인 학습
3350인 학습
180660인 학습
48569인 학습
18603인 학습
40936인 학습
1549인 학습
1183인 학습
32909인 학습
认证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)
大。