算法复杂度 O(NlogN)

原创
2019/05/07 17:20
阅读数 486

算法书上对复杂度的从小到大排序是: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) 的复杂度,已经是很好的了。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部