算法推土机cpu

第2章算法启示算法:算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作.
数据结构大话2.
1开场白各位同学大家好.
上次上完课后,有同学对我说,老师,我听了你的课,感觉数据结构没什么的,你也太夸大它的难度了.
是呀,我好像是强调了数据结构比较搞脑子,而上次课,其实还没拿出复杂的东西来说道.
不是不想,是没必要,第一次课就把你们糊弄晕,那以后还玩什么,逃课的不就更多了吗你们看,今天来的人数和第一次差不多,而且暂时还没有睡觉的.
今天我们介绍的内容在难度上就有所增加了,做好准备了吗2.
2数据结构与算法关系我们这门课程叫数据结构,但很多时候我们会讲到算法,以及它们之间的关系.
市场上也有不少书叫"数据结构与算法分析"这样的名字.
有人可能就要问了,那你到底是只讲数据结构呢,还是和算法一起讲它们之间是什么关系呢干吗要放在一起这问题怎么回答.
打个比方吧,今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院,抬头一看——《梁山伯》18:00开演.
嗯,怎么会是这样一问才知,今天饰演祝英台的演员生病,所以梁山伯唱独角戏.
真是搞笑了,这还有什么看头.
于是你们打算去看爱情电影.
到了电影院,一看海报——《罗密欧》,是不是名字写错了,问了才知,原来饰演朱丽叶的演员因为嫌弃演出费用太低,中途退演了.
制片方考虑到已经开拍,于是就把电影名字定为《罗密欧》,主要讲男主角的心路旅程.
哎,这电影还怎么看啊事实上,数据结构和算法也是类似的关系.
只谈数据结构,当然是可以,我们可以在很短的时间就把几种重要的数据结构介绍完.
听完后,很可能你没什么感觉,不知道这些数据结构有何用处.
但如果我们再把相应的算法也拿来讲一讲,你就会发现,甚至开始感慨:哦,计算机界的前辈们,的确是一些很牛很牛的人,他们使得很多看似很难解决或者没法解决的问题,变得如此美妙和神奇.
也许从这以后,慢慢地你们中的一部分会开始把你们的崇拜对象,从帅哥美女、18第2章算法什么"哥"什么"姐"们,转移到这些大胡子或者秃顶的老头身上,那我就非常欣慰了.
而且,这显然是一种成熟的表现,我期待你们中多一点这样的人,这样我们国家的软件行业,也许就有得救了.
不过话说回来,现在好多大学里,通常都是把"算法"分出一门课单独讲的,也就是说,在《数据结构》课程中,就算谈到算法,也是为了帮助理解好数据结构,并不会详细谈及算法的方方面面.
我们的课程也是按这样的原则来展开的.
2.
3两种算法的比较大家都已经学过一门计算机语言,不管学的是哪一种,学得好不好,好歹是可以写点小程序了.
现在我要求你写一个求1+2+3+……+100结果的程序,你应该怎么写呢大多数人会马上写出下面的C语言代码(或者其他语言的代码):inti,sum=0,n=100;for(i=1;i2时,算法A就开始优于算法B了,随着n的增加,算法A要27数据结构大话越来越好过算法B了(执行的次数比B要少).
于是我们可以得出结论,算法A总体上要好过算法B.
此时我们给出这样的定义,输入规模n在没有限制的情况下,只要超过一个数值N,这个函数就总是大于另一个函数,我们称函数是渐近增长的.
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g().
n从中我们发现,随着n的增大,后面的+3还是+1其实是不影响最终的算法变化的,例如算法A′与算法B′,所以,我们可以忽略这些加法常数.
后面的例子,这样的常数被忽略的意义可能会更明加显.
我们来看第二个例子,算法C是4n+8,算法D是2n2+1(如表2‐8‐2所示).
表2-8-2次数算法C(4n+8)算法C'(n)算法D(2n2+1)算法D'(n2)n=112131n=216294n=3203199n=104810201100n=1004081002000110000n=00014008120000000001100000当n≤3的时候,算法C要差于算法D(因为算法C次数比较多),但当n>3后,算法C的优势就越来越优于算法D了,到后来更是远远胜过.
而当后面的常数去掉后,我们发现其实结果没有发生改变.
甚至我们再观察发现,哪怕去掉与n相乘的常数,这样的结果也没发生改变,算法C′的次数随着n的增长,还是远小于算法D′.
也就是说,与最高次项相乘的常数并不重要.
我们再来看第三个例子.
算法E是2n2+3n+1,算法F是2n3+3n+1(如表2‐8‐3所示).
表2-8-3次数算法E(2n2+3n+1)算法E'(n2)算法F(2n3+3n+1)算法F'(n3)n=16161n=2154238n=32896427n=1023110020311000n=10020301100002000301100000028第2章算法当n=1的时候,算法E与算法F结果相同,但当n>1后,算法E的优势就要开始优于算法F,随着n的增大,差异非常明显.
通过观察发现,最高次项的指数大的,函数随着n的增长,结果也会得长特别.
变增快我们来看最后一个例子.
算法G是2n2,算法H是3n+1,算法I是2n2+3n+1(如表2‐8‐4所示).
表2-8-4次数算法G(2n2)算法H(3n+1)算法I(2n2+3n+1)n=1246n=28715n=5501666n=1020031231n=1002000030120301n=1,000200000030012003001n=10,00020000000030001200030001n=100,0002000000000030000120000300001n=1,000,000200000000000030000012000003000001这组数据应该就看得很清楚.
当n的值越来越大时,你会发现,3n+1已经没法和2n2的结果相比较,最终几乎可以忽略不计.
也就是说,随着n值变得非常大以后,算法G其实已经很趋近于算法I.
于是我们可以得到这样一个结论,判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数.
判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的.
根据刚才的几个样例,我们发现,如果我们可以对比这几个算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的增大,它会越来越优于另一算法,或者越来越差于另一算法.
这其实就是事前估算方法的理论依据,通过算法时间复杂度来估算算法时间效率.
2.
9算法时间复杂度2.
9.
1算法时间复杂度定义在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量29数据结构大话级.
算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n)).
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度.
其中f(n)是问题规模n的某个函数.
这样用大写O()来体现算法时间复杂度的记法,我们称之为大O.
记法一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法.
显然,由此算法时间复杂度的定义可知,我们的三个求和算法的时间复杂度分别为O(n),O(1),O(n2).
我们分别给它们取了非官方的名称,O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶,当然,还有其他的一些阶,我们之后会介绍.
2.
9.
2推导大O阶方法那么如何分析一个算法的时间复杂度呢即如何推导大O阶呢我们给出了下面的推导方法,基本上,这也就是总结前面我们举的例子.
推导大O阶:1.
用常数1取代运行时间中的所有加法常数.
2.
在修改后的运行次数函数中,只保留最高阶项.
3.
如果最高阶项存在且不是1,则去除与这个项相乘的常数.
得到的结果就是大O阶.
哈,仿佛是得到了游戏攻略一样,我们好像已经得到了一个推导算法时间复杂度的万能公式.
可事实上,分析一个算法的时间复杂度,没有这么简单,我们还需要多看几个例子.
2.
9.
3常数阶首先顺序结构的时间复杂度.
下面这个算法,也就是刚才的第二种算法(高斯算法),为什么时间复杂度不是O(3),而是O(1).
intsum=0,n=100;/*执行一次*/sum=(1+n)*n/2;/*执行一次*/printf("%d",sum);/*行次*/执一这个算法的运行次数函数是f(n)=3.
根据我们推导大O阶的方法,第一步就是把常数项3改为1.
在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的30第2章算法时间复杂度为O(1).
另外,我们试想一下,如果这个算法当中的语句sum=(1+n)*n/2有10句,即:intsum=0,n=100;/*执行1次*/sum=(1+n)*n/2;/*执行第1次*/sum=(1+n)*n/2;/*执行第2次*/sum=(1+n)*n/2;/*执行第3次*/sum=(1+n)*n/2;/*执行第4次*/sum=(1+n)*n/2;/*执行第5次*/sum=(1+n)*n/2;/*执行第6次*/sum=(1+n)*n/2;/*执行第7次*/sum=(1+n)*n/2;/*执行第8次*/sum=(1+n)*n/2;/*执行第9次*/sum=(1+n)*n/2;/*执行第10次*/printf("%d",sum);/*执行1次*/事实上无论n为多少,上面的两段代码就是3次和12次执行的差异.
这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶.
注意:不管这个常数是多少,我们都记作O(1),而不能是O(3)、O(12)等其他任何数字,这是初学者常常犯的错误.
对于分支结构而言,无论是真,还是假,执行的次数都是恒定的,不会随着n的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1).
2.
9.
4线性阶线性阶的循环结构会复杂很多.
要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数.
因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况.
下面这段代码,它的循环的时间复杂度为O(n),因为循环体中的代码须要执行n次.
inti;for(i=0;iN,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n).
于是我们可以得出一个结论,判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的,如果我们可以对比算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的变大,它会越来越优于另一算法,或者越来越差于另一算法.
然后给出了算法时间复杂度的定义和推导大O阶的步骤.
37数据结构大话推导大O阶:用常数1取代运行时间中的所有加法常数.
在修改后的运行次数函数中,只保留最高阶项.
如果最高阶项在且不是1,则去除与这个项相乘的常数.
存得到的结果就是大O阶.
通过这个步骤,我们可以在得到算法的运行次数表达式后,很快得到它的时间复杂度,即大O阶.
同时我也提醒了大家,其实推导大O阶很容易,但如何得到运行次数的表达式却是需要数学功底的.
接着我们给出了常见的时间复杂度所耗时间的大小排列:)O(<)!
O(<)O(2<)O(<)O(<)logO(<)O(<)O(log2.
14结尾语很多学生,学了四年计算机专业,很多程序员,做了很长时间的编程工作,却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事.
因为弄不清楚,所以也就从不深究自己写的代码是否效率低下,是不是可以通过优化让计算机更加快速高效.
他们通常的借口是,现在CPU越来越快,根本不用考虑算法的优劣,实现功能即可,用户感觉不到算法好坏造成的快慢.
可事实真是这样吗还是让我们用数据来说话吧.
假设CPU在短短几年间,速度提高了100倍,这其实已经很夸张了.
而我们的某个算法本可以写出时间复杂度是O(n)的程序,却写出了O(n2)的程序,仅仅因为容易想到,也容易写.
即在O(n2)的时间复杂度算法程序下,速度其实只提高了10倍,而对于O(n)复杂度的算法说,那才是真的100倍.
时间来也就是说,一台老式CPU的计算机运行O(n)的程序和一台速度提高100倍新式CPU运行O(n2)的程序.
最终效率高的胜利方却是老式CPU的计算机,原因就在于算法的优劣直接决定了程序运行的效率.
38第2章算法39也许你就可以深刻的感受到,愚公移山固然可敬,但发明炸药和推土机,可能更加实在和聪明(如图2‐14‐1所示).
图2-14-1希望大家在今后的学习中,好好利用算法分析的工具,改进自己的代码,让计算机轻松一点,这样你就更加胜人一筹.
读书笔记1