首页 > 代码库 > 各种时间复杂度到底差别有多大(有图有真相)
各种时间复杂度到底差别有多大(有图有真相)
做算法分析的时候经常用到各种时间复杂度如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)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。