欢迎来到天天文库
浏览记录
ID:39396450
大小:43.50 KB
页数:11页
时间:2019-07-02
《算法与程序设计复习总结》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法与程序设计复习总结1、算法一个算法是一个有穷规则的集合,其中规则规定了解决某一特定问题的运算序列。算法特性:有穷性、确定性、可行性、输入、输出。2、 时间复杂度设n为被求解问题的规模,则用n的函数表示执行算法所需的时间,称为算法的时间复杂度。渐进时间复杂性n>n0n→∞若limT(n)/g(n)=1,则称T(n)渐进于g(n),记为T(n)~o(g(n)) 3、 时间复杂性的上下界及阶若存在常数c、c1、c2和n0,对所有的n>n0,有①
2、T(n)
3、≤c
4、g(n)
5、,则称g(n)为T(n)的上界,记为
6、T(n)=O(g(n))。②
7、T(n)
8、≥c
9、g(n)
10、,则称g(n)为T(n)的下界,记为T(n)=Ω(g(n))。③c1
11、g(n)
12、≤T(n)≤c2
13、g(n)
14、,则称T(n)与g(n)同阶,称g(n)是T(n)的精确界。 记为T(n)=θ(g(n)),等价于T(n)=O(g(n))且T(n)=Ω(g(n)),还等价于T(n)=O(g(n))且g(n)=O(T(n))。4、 TSP(TravellingSalesmanProblem)旅行商问题设有n个城市,分别用1、2、3、4…n表示,从城市i到城市j的
15、距离为dij ,一个推销员要从城市1开始,到达其他任何一个城市一次且仅到达一次,最后返回城市1。问题是他应如何选择行走路线,使总的路径最短。5、 RASP(Random Access Stored Program)随机存储存取程序RASP程序存放在存储器中,能修改自身,无间接寻址,每条指令占两个存储单元,第一个存放操作码,第二个存放操作数。6、 P类问题:一类能够用确定性算法在多项式时间内求解的问题7、 NP类:一类能够用非确定性算法在多项式时间内求解的问题。8、 NP难度:一个问题可在多项式时间内转化
16、成为一个NP问题,但是不能证明该问题是NP问题,但是至少可以证明该问题的难度相当于一个NP问题,称该问题具有NP难度。9、 NPC类:NP完全类。设在NP问题中存在某问题c,所有其他NP问题都可以在多项式时间内转化为问题c,则称c是NP完全的。NPC={c
17、c∈NP并且所有a∈NP,a∝c}10、EREW单读单写EREW(Exclusive-ReadandExclusive-Write )并读单写CREW(Concurrent-ReadandExclusive-Write)单读并写ERCW(Exclusive
18、-ReadandConcurrent-Write)并读并写CRCW(Concurrent-ReadandConcurrent-Write)11、SM共享存储器12、SIMDSISD:单指令流单数据流MISD:多指令流单数据流SIMD:单指令流多数据流MIMD:多指令流多数据流⒈T(n)=3T(n/2)+kn,T(1)=kT(n)=32T(n/22)+3kn/2+kn=33T(n/23)+32kn/22+3kn/2+knm-1 i=0=3mT(n/2m)+kn∑(3/2)i =3mT(n/2m)+kn{[1-(
19、3/2)m]/[1-3/2]}令n=2m m=logn T(n)=k3m-2k(2m-3m)=O(3m)=O(3logn)=O(nlog3)换底公式解法2:(讲义—可乘函数) 令T(n)=kU(n)∴U(1)=1 ∴kU(n)=3kU(n/2)+kn∴U(n)=3kU(n/2)+n 此时n是可乘函数,a=3,b=2,d(2)=220、)=O(n1.59)⒉T(n)=n1/2T(n1/2)+n,T(1)=1 =n1/2(n1/4T(n1/4)+n1/2)+n =n(1/2+1/22+…+1/2i)+in =n(1-1/2i)+in另解:令T(n)=nU(logn)⒊T(n)=aT(n-1)+bn,T(1)=1⑴T(n)=O(?)。⑵讨论:当a<1,a=1,a>1三种情况下,T(n)=O(?)。T(n)=a2T(n-2)+ab(n-1)+bn=a3T(n-3)+a2b(n-2)+ab(n-1)+bnk-1 i=0=akT21、(n-k)+b∑ai(n-i) 令n-k=1 k=n-1当a=1,T(n)=1+b(n+2)(n-1)/2如果a=1T(n)=O(n2)k-1k-1当a≠1, i=0T(n)=akT(n-k)+nb∑(ai)-b∑(iai)i=0k-1 令A=∑(iai)=0+a+2a2+3a3+…+(k-2)ak-2+(k-1)ak-1i=0 aA=0+a2+2a3+…(k-2)ak-1+(
20、)=O(n1.59)⒉T(n)=n1/2T(n1/2)+n,T(1)=1 =n1/2(n1/4T(n1/4)+n1/2)+n =n(1/2+1/22+…+1/2i)+in =n(1-1/2i)+in另解:令T(n)=nU(logn)⒊T(n)=aT(n-1)+bn,T(1)=1⑴T(n)=O(?)。⑵讨论:当a<1,a=1,a>1三种情况下,T(n)=O(?)。T(n)=a2T(n-2)+ab(n-1)+bn=a3T(n-3)+a2b(n-2)+ab(n-1)+bnk-1 i=0=akT
21、(n-k)+b∑ai(n-i) 令n-k=1 k=n-1当a=1,T(n)=1+b(n+2)(n-1)/2如果a=1T(n)=O(n2)k-1k-1当a≠1, i=0T(n)=akT(n-k)+nb∑(ai)-b∑(iai)i=0k-1 令A=∑(iai)=0+a+2a2+3a3+…+(k-2)ak-2+(k-1)ak-1i=0 aA=0+a2+2a3+…(k-2)ak-1+(
此文档下载收益归作者所有