算法书上对复杂度的从小到大排序是:O(logN)
, O(N)
, O(NlogN)
, O(N^2)
, O(N^3)
....
今天突然想到了一个问题,到底 O(NlogN)
会比 O(N)
慢多少呢?
logN
呗
这个答案不能算错,但是并不直观,我们求助一下数学上的图像
比较直观了,但是最终有多大影响呢,再来看一下 2^N
对应的值
2^1 = 2
2^2 = 4
2^4 = 16
2^8 = 256
2^16 = 65,536
2^32 = 4,294,967,296
2^64 = 18,446,744,073,709,551,616
2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456
2^256 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936
目前预测的宇宙的原子总数量级为 10^80
,基于 2^10 = 10^3
转换,宇宙原子总数量级约为 2^267
, 因此可以说,logN
的极限值是267
。 这个值相对于数据规模来说,已经可以忽略不计了,应用复杂度的计算原则来说,logN
是可以当作一个常数舍弃掉的(当然实际上不可以)。
所以,如果一个算法能有 O(NlogN)
的复杂度,已经是很好的了。