算法与程序设计复习总结

《算法与程序设计复习总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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）=2

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+(