算法设计与分析复习.doc

算法概述 算法是若干指令的有穷序列，满足性质： (1)输入(2)输出 (3)确定性 (4)有限性。 算法复杂性分析主要包括空间复杂性和时间复杂性。 算法复杂性分析 （1）渐近上界记号O O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n3 n0有：0 ￡ f(n) ￡ cg(n) } （2）渐近下界记号W W (g(n)) = { f(n) | 存在正常数c和n0使得对所有n3 n0有：0￡ cg(n) ￡ f(n) } （3）紧渐近界记号Q Q (g(n)) = { f(n) | 存在正常数c1,c2和n0使得对所有n3 n0有：c1g(n) ￡ f(n) ￡ c2g(n) } 定理1： Q (g(n)) = O (g(n)) ? W (g(n)) 最常见的多项式时间算法的渐近时间复杂度 O(1)＜O(log n)＜O(n)＜O(nlog n)＜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难度（NP hard）的。 其中∝表示约化，Q1∝Q，表示Q1可以在多项式时间转化为问题Q，从而可通过调用问题Q的算法求解。 （NP完全）对于问题Q?NP，Q是NP难度的，则称Q是NPC（NP complete）的。 P NP NPC的关系 第2章 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 2.2 分治法的基本思想 divide-and-conquer(P) { if ( | P | = n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } 在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。 分治法所能解决的问题一般具有以下几个特征： (1)该问题的规模缩小到一定的程度就可以容易地解决； (2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质. (3)利用该问题分解出的子问题的解可以合并为该问题的解； (4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 2.4 大整数的乘法 X = a2n/2 + b Y = c2n/2 + d 1. XY = ac2n + (ad+bc) 2n/2 + bd (O(n2)) 2. XY = ac2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd T(n)=O(nlog3) 2.8 快速排序 基本思想： templateclass Type void QuickSort (Type a[], int p, int r) { if (pr) { int q=Partition(a,p,r); QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 } } 掌握Partition(a,p,r)方法。 平均情况复杂性O(nlogn) 2.9 线性时间选择 templateclass Type Type RandomizedSelect(Type a[],int p,int r,int k) { if (p==r) return a[p]; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j); } 在最坏情况下，算法randomizedSelect需要O(n2)计算时间。但算法randomizedSelect可以在O(n)平均时间内找