算法导论复习第一章算法概述1、算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。2、算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。3、在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}（2）渐近下界记号(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}（3）非紧上界记号oo(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)<cg(n)}等价于f(n)/g(n)0，asn。（4）非紧下界记号(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)<f(n)}等价于f(n)/g(n)，asn。f(n)(g(n))g(n)o(f(n))（5）紧渐近界记号(g(n))={f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}定理1：(g(n))=O(g(n))(g(n))（1）传递性：f(n)=(g(n))，g(n)=(h(n))f(n)=(h(n))；f(n)=O(g(n))，g(n)=O(h(n))f(n)=O(h(n))；f(n)=(g(n))，g(n)=(h(n))f(n)=(h(n))；（2）反身性：f(n)=(f(n))；f(n)=O(f(n))；f(n)=(f(n)).（3）对称性：f(n)=(g(n))g(n)=(f(n)).（4）互对称性：f(n)=O(g(n))g(n)=(f(n))；f(n)=o(g(n))g(n)=(f(n))；（5）算术运算：O(f(n))+O(g(n))=O(max{f(n),g(n)})；O(f(n))+O(g(n))=O(f(n)+g(n))；O(f(n))*O(g(n))=O(f(n)*g(n))；O(cf(n))=O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=O(f(n))。★规则O(f(n))+O(g(n))=O(max{f(n),g(n)})的证明：对于任意f1(n)O(f(n))，存在正常数c1和自然数n1，使得对所有nn1，有f1(n)c1f(n)。类似地，对于任意g1(n)O(g(n))，存在正常数c2和自然数n2，使得对所有nn2，有g1(n)c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。则对所有的nn3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n))c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).4、能求解一个算法的时间复杂度第二章递归与分治策略1、分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2、分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3、（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。4、二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法的while循环，待搜