算法设计与分析_总结7.docVIP

： 算法定义：算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 程序定义：程序是算法用某种程序设计语言的具体实现。可以不满足算法的性质(4)。 算法复杂性分为时间复杂性和空间复杂性。 可操作性最好且最有使用价值的是最坏情况下的时间复杂性。 O(n)定义：存在正的常数C和自然数N0，当N=N0时有f(N)=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=O(g(n)). ?(n)定义：存在正的常数C和自然数N0，当N=N0时有f(N)=Cg(N),则称函数f(N)当N充分大时有上界，记作f(N)=?(g(n)). (n)定义:当f(n)=O(g(n))且f(N)=?(g(n))，记作f(N)=(g(n))，称为同阶。 求下列函数的渐进表达式：3n2+10n ~~~O(n2) n2/10+2n~~~O(2n) 21+1/n~~~O(1) logn3~~~O(logn) 10log3n~~~O(n) 从低到高渐进阶排序：2 logn n2/3 20n 4n2 3n n! ： 分治法的设计思想：将一个难以直接解决的问题，分割成一些规模较小的相同问题，以便各个击破分而治之。 例1 Fibonacci数列 代码（注意边界条件）。 int fibonacci(int n) { if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } Ackerman函数双递归。 A(1,1)代入求值。 A(1,1)=A(A(0,1),0)=A(1,0)=2 全排列的递归算法代码。 void Perm(int a[],int n,int k) { if(n==k){ for(int i=0;in;i++) couta[i]” ”; coutendl; return ; } for(int i=k;in;i++){ Swap(a[i].a[k]); Perm(a,n,k+1); Swap(a[i],a[k]); } return ; } Hanoi塔问题的递归算法与时间复杂度。 void Hanoi(int n,int from,int to,int other)//将n个盘子从from借助other到达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) 整数划分问题的递归公式。 分解整数n为n1,n2…,以降序排列，q(n,m)表示最大的n1=m的划分方法数。 q(n,m)= T(n)=kT(n/m)+nd 。k表示划分子问题的个数，m表示减小问题的规模，nd表示分割组合子问题所需的时间复杂度。 结论： 二分有哪些信誉好的足球投注网站代码及变形P35(答案是FFFFTFF)。 int BinarySearch(int a[], int x, int l, int r)//a数组的有哪些信誉好的足球投注网站边界为[l,r] { while (r = l){ int m = (l+r)/2; if (x == a[m]) return m; if (x a[m]) r = m-1; else l = m+1; } return -1; } 大整数乘法及Strassen矩阵乘法的时间复杂度。（运用本节7的结论） 大整数乘法将X=[A B],Y=[C D]。XY=AC2N+((A-B)(D-C)+AC+BD)2N/2+BD（不记）。子问题个数k为三次乘法AC\BD\(A-B)(C-D),问题规模减小了一半，即m=2。分开合并花费O(n).所以，时间复杂度为O(nlog3). Strassen矩阵乘法将矩阵以“田”字分割矩阵后相乘， T(n)=7T(n/2)+O(n2)，所以时间复杂度为O(nlog7). 棋盘覆盖过程及时间复杂度。 有一个2k*2k的特殊方格地面，因为它有一个地板不能铺设，用黑色标出。现在