首页 > 代码库 > 各种时间复杂度到底差别有多大(有图有真相)

各种时间复杂度到底差别有多大(有图有真相)

做算法分析的时候经常用到各种时间复杂度如O(n), O(logn), O(nlogn), O(n^2), ... 它们之间到底有多大的差别呢?下面这张图是一个直观的表达:

放大来看logn, n, 和nlogn的情况:

可见,如果我们能将时间复杂度从从O(n^2)减到到O(n),或从从O(n)减到到O(logn),都是性能上一个大的飞跃。

 

从另一个角度而言,大于O(n^2)或O(n^3)时间复杂度的程序实际上都是不可用的。根据维基百科,现在最强的CPU每秒大概可执行428亿条指令(4*10^10),而对于一个O(2^n)的程序,当n=100时,就算有2^100条指令,这样的CPU大概要算1万亿年(10^12)。