算法设计与分析_总结7

《算法设计与分析_总结7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章：1.算法定义：算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。2.程序定义：程序是算法用某种程序设计语言的具体实现。可以不满足算法的性质(4)。3.算法复杂性分为时间复杂性和空间复杂性。4.可操作性最好且最有使用价值的是最坏情况下的时间复杂性。5.O(n)定义：存在正的常数C和自然数N0，当N>=N

2、0时有f(N)<=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=O(g(n)).6.Ω(n)定义：存在正的常数C和自然数N0，当N>=N0时有f(N)>=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=Ω(g(n)).7.(n)定义:当f(n)=O(g(n))且f(N)=Ω(g(n))，记作f(N)=(g(n))，称为同阶。8.求下列函数的渐进表达式：3n2+10n~~~O(n2)n2/10+2n~~~O(2n)21+1/n~~~O(1)logn3~~~O(logn)10

3、log3n~~~O(n)9.从低到高渐进阶排序：2lognn2/320n4n23nn!第二章：1.分治法的设计思想：将一个难以直接解决的问题，分割成一些规模较小的相同问题，以便各个击破分而治之。2.例1Fibonacci数列代码（注意边界条件）。intfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}3.Ackerman函数双递归。A(1,1)代入求值。A(1,1)=A(A(0,1),0)=A(1,0)=24.全排

4、列的递归算法代码。voidPerm(inta[],intn,intk){if(n==k){for(inti=0;i

5、达to{if(n<=0)return;Hanoi(n-1,from,other,to);//将n-1个盘子从from借助to到达other,此时n-1个盘子都在other上，1//个盘子在from上。Move(1,from,to);//将from上的那个盘子移动到to上。此时from为空。Hanoi(n-1,other,to,from);//将other上的n-1个盘子借助from移动到to上。此时to上有n个盘子。}O(2n)2.整数划分问题的递归公式。分解整数n为n1,n2…,以降序排列，q(n,

6、m)表示最大的n1<=m的划分方法数。q(n,m)=3.T(n)=kT(n/m)+nd。k表示划分子问题的个数，m表示减小问题的规模，nd表示分割组合子问题所需的时间复杂度。结论：4.二分搜索代码及变形P35(答案是FFFFTFF)。intBinarySearch(inta[],intx,intl,intr)//a数组的搜索边界为[l,r]{while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x

7、5.大整数乘法及Strassen矩阵乘法的时间复杂度。（运用本节7的结论）大整数乘法将X=[AB],Y=[CD]。XY=AC2N+((A-B)(D-C)+AC+BD)2N/2+BD（不记）。子问题个数k为三次乘法ACBD(A-B)(C-D),问题规模减小了一半，即m=2。分开合并花费O(n).所以，时间复杂度为O(nlog3).Strassen矩阵乘法将矩阵以“田”字分割矩阵后相乘，T(n)=7T(n/2)+O(n2)，所以时间复杂度为O(nlog7).1.棋盘覆盖过程及时间复杂度。有一个2k*2

8、k的特殊方格地面，因为它有一个地板不能铺设，用黑色标出。现在用如下四种地板进行铺设。原图，田字划分后在中间位置铺设一块地板，使得每个四分之一部分都有一块被涂色的地板。将问题分成了4个相同的子问题。在每个四分之一部分，重复进行田字划分和中间铺设地板，最终可以完成该问题。N=2k,K=4,m=2,合并分解复杂度为O(1),所以T(n)=O((2k)log24)=O(4k)2.合并排序、快速排序、线性时间选择的思想、代码、时间复杂度。合并排序O(nlogn)：