算法设计与分析复习VIP免费

第1章算法概述算法是若干指令的有穷序列，满足性质：(1)输入(2)输出(3)确定性(4)有限性。算法复杂性分析主要包括空间复杂性和时间复杂性。算法复杂性分析（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）紧渐近界记号(g(n))={f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}定理1：(g(n))=O(g(n))(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以及任意问题Q1NP，都有Q1∝Q，则Q是NP难度（NPhard）的。其中∝表示约化，Q1∝Q，表示Q1可以在多项式时间转化为问题Q，从而可通过调用问题Q的算法求解。（NP完全）对于问题QNP，Q是NP难度的，则称Q是NPC（NPcomplete）的。PNPNPC的关系第2章递归与分治策略分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2.2分治法的基本思想divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。分治法所能解决的问题一般具有以下几个特征：(1)该问题的规模缩小到一定的程度就可以容易地解决；(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质.(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,intr){if(pTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i-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小元素。进一步改进：将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。所以按此基准划分所得的2个子数组的长度都至少缩短1/4。第3章动态规划算法的思想:动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态算法基本步骤：(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。3.1...