算法设计与分析复习

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

1、第1章算法概述算法是若干指令的有穷序列，满足性质：(1)输入(2)输出(3)确定性(4)有限性。算法复杂性分析主要包括空间复杂性和时间复杂性。算法复杂性分析（1）渐近上界记号OO(g(n))={f(n)

2、存在正常数c和n0使得对所有n³n0有：0£f(n)£cg(n)}（2）渐近下界记号WW(g(n))={f(n)

3、存在正常数c和n0使得对所有n³n0有：0£cg(n)£f(n)}（3）紧渐近界记号QQ(g(n))={f(n)

4、存在正常数c1,c2和n0使得对所有n³n0有：c1g(n)£f(n)£c2g(n)}

5、定理1：Q(g(n))=O(g(n))ÇW(g(n))最常见的多项式时间算法的渐近时间复杂度O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)最常见的指数时间算法的渐近时间复杂度O(2n)＜O(n！)＜O(nn)通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。NP完全性理论P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。（NP难度）对于问题Q

6、以及任意问题Q1ÎNP，都有Q1∝Q，则Q是NP难度（NPhard）的。其中∝表示约化，Q1∝Q，表示Q1可以在多项式时间转化为问题Q，从而可通过调用问题Q的算法求解。（NP完全）对于问题QÎNP，Q是NP难度的，则称Q是NPC（NPcomplete）的。PNPNPC的关系8/8第2章递归与分治策略分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2.2分治法的基本思想divide-and-conquer(P){if(

7、P

8、<=n0)adhoc(P);//解决小

9、规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。分治法所能解决的问题一般具有以下几个特征：(1)该问题的规模缩小到一定的程度就可以容易地解决；(2)该问题可以分

10、解为若干个规模较小的相同问题，即该问题具有最优子结构性质.(3)利用该问题分解出的子问题的解可以合并为该问题的解；(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。2.4大整数的乘法X=a2n/2+bY=c2n/2+d1.XY=ac2n+(ad+bc)2n/2+bd(O(n2))2.XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdT(n)=O(nlog3)2.8快速排序基本思想：templatevoidQuickSort(Typea[],intp

11、,intr){if(pTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i

12、-p+1;if(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}在最坏情况下，算法randomizedSelect需要O(n2)计算时间。但算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。进一步改进：l将n个输入元素划分成én/5ù个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共én/5ù个。l递归调

13、用select来找出这én/5ù个元素的中位数。如果én/5ù是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。l所以按此基准划分所得的2个子数组的长度都至少缩短1/4。第3章动态规划算法的思想:动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解