关于小悟志网站地图归档友情链接联系Feed

云上小悟 + 

首页 » InfoTech »

算法的时间复杂度

2017年10月2日 / 37次阅读

我们研究算法的时候,有一个重要的指标,就是这个算法的时间复杂度(Order of magnitude)是什么,以此来衡量这个算法是否在实际应用中可以被接受。

算法的时间复杂度并不是表示一个算法程序解决问题需要具体花多少时间,而是表示当问题规模变化后,算法程序需要的时间长度的变化程度。比如问题规模是\(n\),对应此问题的算法的时间复杂度是\(O(f(n))\)。\(O\)就是Order的第一个字母。(衡量算法性能还有一个空间复杂度指标,本文不涉及)

对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个算法程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。

不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序性能很好,具有\(O(1)\)的时间复杂度,也称常数级复杂度。

数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是\(O(n)\),比如找出\(n\)个数中的最大值。这种算法的时间复杂度随问题规模同比例变化。

而像冒泡排序,插入排序等算法,数据扩大2倍,时间变慢4倍的,其算法的时间复杂度就是\(O(n^2)\)。

还有一些穷举类的算法,所需时间长度成几何阶数上涨,其算法的时间复杂度为\(O(a^n)\),称为指数级复杂度,甚至会是\(O(n!)\)的阶乘级复杂度。

算法的时间复杂度的确定过程中,含有在\(n \to +\infty\)时,取时间复杂度表达式主部的环节,这也就是表示,算法的时间复杂度,只是表示一个数量级上的变化关系,符合其英文原意。因此,不会存在\(O(2 \times n^2)\)的时间复杂度,因为前面的那个\(2\)是多余的系数,根本不会影响到数量级这个层面。同理,\(O(n^3+n^2)\)的时间复杂度也就是\(O(n^3)\)。

因此我们说,一个拥有\(O(0.01 \times n^3)\)时间复杂度的程序的效率比\(O(100 \times n^2)\)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终\(O(n^3)\)的时间复杂度将远远超过\(O(n^2)\)。我们也说,\(O(n^{100})\)的复杂度小于\(O(1.01^n)\)的复杂度。

容易看出,前面的几类时间复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者:一种是\(O(1)\),\(O(log(n))\),\(O(n^a)\)等,我们把它叫做多项式级的时间复杂度,因为它的规模\(n\)出现在底数的位置;另一种是\(O(a^n)\)和\(O(n!)\)型复杂度,它是非多项式级的时间复杂度,这样的复杂度在问题规模很大的时候,计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

自然地,人们会想到一个问题:会不会所有的问题都可以找到时间复杂度为多项式级的算法呢?

很遗憾,答案是否定的。

有些问题甚至根本不可能找到一个正确的算法,这些问题称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题。

再比如,输出从1到n这n个数的全排列。不管你用什么算法,你的复杂度都是阶乘级,因为你总得用阶乘级的时间打印出结果来。有人说,这样的“问题”不是一个“正规”的问题,正规的问题是让程序解决一个问题,输出一个“YES”或“NO”(这被称为判定性问题),或者一个什么什么的最优值(这被称为最优化问题)。那么,根据这个定义,我也能举出一个不大可能会有多项式级算法的问题来:Hamilton回路。问题是这样的:给你一个图,问你能否找到一条经过每个顶点一次且恰好一次(不遗漏也不重复)最后又走回来的路(满足这个条件的路径叫做Hamilton回路)。这个问题现在还没有找到多项式级的算法。

关于算法的时间复杂度,本文的内容应该足够深刻理解了,涉及到一些数学知识是必须的,数学是算法的基础。

本文链接:http://www.maixj.net/ict/suanfa-shijian-fuzadu-16616
云上小悟 麦新杰(QQ:1093023102)

相关文章

评论是美德

《算法的时间复杂度》有3条评论

无力满足评论实名制,评论对非实名注册用户关闭,有事QQ:1093023102.

  • 麦新杰

    根据斯特林公式,n! 相当于指数级别的增长。当 n 特别小时,多项式级的算法已经快过指数级的算法。当 n 非常大时,人类根本看不到指数级复杂度算法结束的那天。自然的,大家会对多项式级别的算法抱有好感,希望对每一个问题都能找到多项式级别的算法。问题是——每个问题都能找到想要的多项式级别的算法吗? [ ]

  • 麦新杰

    云上小悟二维码 [ ]

  • 麦新杰

    算法推动人类进步。 [ ]


前一篇:
后一篇:

栏目精选

云上小悟,麦新杰的独立博客

栏目


©Copyright 麦新杰 Since 2014 云上小悟独立博客版权所有 备案号:苏ICP备14045477号-1。云上小悟网站部分内容来源于网络,转载目的是为了整合信息,收藏学习,服务大家,有些转载内容也难以判断是否有侵权问题,如果侵犯了您的权益,请及时联系站长,我会立即删除。

网站二维码
拍拍贷
go to top