您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

内功修炼之渐进符号

编程 296℃ 0 3年前 (2014-11-24)

我们分析一个算法的时候,常常需要用到数学去描述时间方面的其性能。在描述的时候我们常常提到渐进符号,最见的是Θ和O(读作大O)。比如在一段程序中有

For(I = 0,I < n ; I ++)

       For (J = 0; j < n ; j++);

For (cnt = 0; cnt < n ; cnt ++);

我们会说其最坏情况是n^2 + n,这时候,实际上我们没有考虑机器因素,我们把每一条指令的执行时间都当做单位1来看,如果我们考虑到机器因素,比如在A机器上,每条指令执行的速度是c1,那么他的最坏情况是 ( n^2  +  n) / c1,而在机器B上,速度变成了c2,那么最坏情况变成了( n^2 + n) / c2,如果c1是10,而c2是20,那么我们就说:算法在机器A上面的性能比机器B上差?显然不是这样的,机器变差了但算法本身没有变差,所以说在不同的机器上跑同样的算法,最坏情况时间总是不一样的,我们得想方设法去除机器性能的影响,而只是去单单分析算法本身的优劣,以便于在具体量化算法性能的时候又能去除机器因素的影响,因为我们讲算法分析而不是计算机系统分析。于是有人发明了Θ符号。对于这个符号我们来看几个例子,再看定义

比如说 :

a * x ^2 + b * x + c = f(x);那么有Θ(x^2) = f(x).

a * x ^ 3 + b * x ^ 2 + c * x + d = f(x);那么有Θ(x ^ 3) = f(x).

也就是说它相当于取出 f(x)的最高次项然后去掉其常数因子,然后放入Θ()中,而放入Θ()中又表示了什么呢?为了弄清楚这个问题,我们来看其定义:

注:在集合表示中“:”符号表示“满足于 …条件”

Θ(g(n)) = {f(n) : 存在某个常数c1,c2,和n0,使得当n >= n0时,有 0 <= c1 * g(n) <= f(n) <= c2 * g(n) }

从后面半句开始,“存在 n > n0,0 <= c1 * g(n)”这里保证了g(n)是一个增函数。接着,有 c1 * g(n) <=  f(n)  <= c2 * g(n).在脑海里可以想象出来函数图像 [ c1 * g(n), c2 * g(n) ]这个区间实际上是摇摆的曲线,如果把g(n)看做是y = x这样的正比例函数,就是一个扇形是吧?一根曲线摇摆着,扫出一个扇形来。而f(n)就是这组成扇形的众多曲线中的一根!这里也就是说,无论g(n)是什么,总能有一个常数因子使得c1 * f(n) = g(n).再返回来原来的题目中去理解:

a * x ^2 + b * x + c = f(x);那么有Θ(x^2) = f(x),这里Θ(x^2)表示,在x趋于无穷大这个过程中,有一个常数c使得c * n^2 = a * x ^2 + b * x + c = f(x),也就是:同!阶!数!(见高数上);这样,我们用Θ()来描述先程序的性能n^2 + n变成了Θ(n ^ 2),这里表明,在n趋于无穷大的过程中,总有一个常数因子使得c * n^2 = n ^ 2 + n,这个常数因子c在上文中说到,由机器和其它非算法因素来决定。也就是说,我们用Θ(n ^ 2)来表示一个算法的性能的时候,我们就完全忽略了机器,只研究算法本身,它好像是说:无论你在什么机器上跑这个算法,只要输入规模足够大,你的性能都是n ^ 2的整数倍,至于是多少倍,由机器决定的,反正在同样的机器上,这个倍数是相等了。

你看,Θ(x^2)表示的不就是机器无关的,纯算法的性能了吗?原来的问题解决了。不过Θ(x^2)符号还使得我们只关注最高次幂,不去关注低次项,因为在n->无穷大的时候,低次项是没有意义的,因为此时只要n变化一点点,就足以抵消低次项的变化(其实还是同阶数)。所以我们知道,对于一个时间复杂度为Θ(x^2)的算法,它的时间性能是优于Θ(x^3)的算法的,这里我们没有考虑常数因子,即使Θ(x^3)的常数因子是10000000000000而Θ(x^2)的常数因子是1也没有关系,因为无论如何,总有一个值n0使得n越过这个点之后Θ(x^2)的算法总能打败Θ(x^3)的算法,也就是说使用了Θ这类的符号(渐进符号)去比较算法时间性能的时候,是与机器无关的,即使你在超级计算机上跑Θ(x^3)算法,只要输入规模和时间足够,跑Θ(x^2)算法的老式386机子总能打败超级计算机。类似于Θ符号我们引出了O符号(读作大o)。

O(g(n)) = {f(n) : 存在某个常数c,和n0,使得当n >= n0 时,有 0 <= f(n) <= c * g(n) }

这里我们就只关心最坏情况,我们在谈论一个算法的最坏情况时间复杂度的时候总是喜欢使用O符号,我通过前面的例子来说明这个O符号的作用。

For(I = 0,I < n ; I ++)

       For (J = 0; j < n ; j++);

For (cnt = 0; cnt < n ; cnt ++);

这时候我们把机器执行的速度看做单位1,于是执行的时间是n^2 + n,我们会说,上面这个算法最坏情况时间复杂度是O(n^2),还是同样的目的,我们不去考虑机器本身的影响,因为机器执行的速度如果是c,那么时间也就是变成了(n^2 + n) / c,也只是常数因子的问题而已。在输入规模足够大的情况下,我们用O(n ^ 2)来忽略机器的影响,只考虑算法本身的最坏情况,告诉别人: 嘿!无论你在什么机器上跑,你的最坏情况都不能比n ^ 2 这个值的x倍更坏啦。至于X倍是多少倍,反正我们只是研究算法的,只有做机器的人才知道X是多少倍,而我们比较算法的时候,不会在不同的机器上去测同样的算法然后拿来比较,往往在同样的机器上去考察一个算法,这时常数因子X是相等的,关心它也是多余的了,这就好比我们高考的时候每个人的分数都乘以10分然后再来报考,结果还不是一样?因为考大学是根据排名来录取的,所以对于算法也是一样的,我们只关注:“那个算法才是最好的?我们应该选择哪个算法?”这种比较性的问题。

 

 

                   ————————————————————————上大人孔乙己 2014、11、23

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?