算法设计与分析算法分析方法一. 算法复杂性分析 v算法复杂性 = 算法所需要的计算机资源v算法的时间复杂性T (n)；v算法的空间复杂性S (n)。v算法的处理器复杂性P (n)v其中 n 是问题的规模（输入大小）。算法对大小为n的所有 实例所需时间的最大 者1. 算法的时间复杂性v最坏情况下的时间复杂性Tmax(n) = max T(I) | size(I)=n v最好情况下的时间复杂性Tmin(n) = min T(I) | size(I)=n v平均情况下的时间复杂性Tavg(n) =v 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。2. 复杂性的渐近性质vT (n) , as n ;v(T (n) t (n) )/ T (n) 0 ，as n;vt (n)是T (n)的渐近性态，称为算法的渐近复杂性。v在数学上， t (n)是T (n)的渐近表达式，是T (n)略去低阶项留下的主项。它比T (n) 简单。v例T(n)=3n2+4nlog2n+7t(n)=3n2(T(n)-t(n)/T(n) = (4nlog2n+7)/ (3n2+4nlog2n+7) 0as n lim (3n2+4nlog2n+7) n n2t(n)=O(n2) =33. 渐近上界记号O设f(n)和g(n)是将非负整数映射为实数的函数。如果存在实常数c 0 和整常数n0 1， 对于每个n n0的整数，满足0 f (n) cg (n) ，则称f(n)是O(g(n)。也可读作“f(n)是g(n)的大O”或“f(n)是g(n)阶的”。渐近上界记号O例1-1 7n-2是O(n) 。证明：由大O的定义可知，需要找一个实常数c 0 和整常数n0 1，对于每个n n0的整数，满足7n-2 cn。容易看出，一种可能的选择是c=7和n0=1，实际上，这只是无数个可选方式之一，因为任何大于7的实数c，以及任何大于或等于1的整数n0都会满足条件。渐近上界记号O例1-2 20n3+10nlogn+5是O(n3) 。证明：对于n 1， 20n3+10nlogn+5 35n3。实际上， aknk+ak-1nk-1+a0总是O(nk)的。渐近上界记号O例1-3 3logn+loglogn是O(logn) 。证明：对于n 2， 3logn+loglogn 4logn。因为对于n=1,loglogn无意义。渐近上界记号O例1-4 2100是O(1) 。证明：对于n 1， 2100 2100 *1。因为，变量n并没有出现在不等式中，我们处理的是恒定值函数。大O符号的使用因为大O符号已经代表“小于或等于”概念，不写成“f(n) O(g(n)”。同样尽管“f(n)=O(g(n)”这种说法很常见，但它并不完全正确（就通常理解的“=”关系而言），而且“f(n) O(g(n)或“f(n)O(g(n)”实际上都不正确。最好说“f(n)是O(g(n)”。如果更偏向于用数学语言，称 f(n) O(g(n)也是正确的。因为大O表示从技术上说定义了函数的全集。渐近分析的记号（1）O(f)+O(g)=O(max(f,g)（2） O(f)+O(g)=O(f+g)（3） O(f)O(g)=O(fg)（4）如果g(n)=O(f(n)，则O(f)+O(g)=O(f)（5） O(cf(n)=O(f(n)，其中c是正常数（6）f=O(f)n规则O(f(n)+O(g(n) = O(max(f(n),g(n) 的证明：v对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n) 。v类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。v令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。v则对所有的 n n3，有vf1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n)= 2c3h(n) = O(max(f(n),g(n) . 与大O相关的渐近符号大和大设f(n)和g(n)是将整数映射为实数的函数。如果存在实常数c 0 和整常数n0 1， 对于n n0，满足 f (n) cg (n) ，则称f(n)是(g(n)(读作“f(n)是g(n)的大”)。在渐近意义上， 的定义可用来表示一个函数大于或等于另一个函数的常数倍。同样，如果f(n)是O(g(n)且f(n)是(g(n)，则称f(n)是(g(n) .(读作“f(n)是g(n)的大”)。即，存在实常数c0和c”0，以及整常、数n0 1，对于n n0,，满足cg(n) f(n)c”g(n)3. 渐近下界记号例1-5 3logn+loglogn是 (logn) 。证明： 3logn+loglogn 3logn,对于n 2。这个例子表明，在用大建立下界时，低阶项可以忽略。4. 紧渐近界记号例1-6 3logn+loglogn是(logn) 。证明： 由例1-3和例1-5可得。与大O相关的渐近符号小o和小设f(n)和g(n)是将整数映射为实数的函数。对于任意常数c 0，存在常数n0 0， 对于n n0，满足 f (n) cg (n) ，则称f(n)是o(g(n)(读作“f(n)是g(n)的小o”)。若对于任意常数c 0，存在常数n0 0， 对于n n0，满足 cg (n) f(n) ，则称f(n)是(g(n) (读作“f(n)是g(n)的小”)。直观上讲，o(.)在渐近意义上类似“小于”， (.)在渐近意义上类似“大于”。非紧上界记号o与非紧下界记号 例1-7 f(n)=12n2+6n是o(n3)和 (n)首先证明f(n)是O(n3).设c（0）为常数，如果取n0=(12+6)/c.那么，对于n n0，可得 cn3 12n2+6n2 12n2+6n因此，f(n)是o(n3）。下面证明f(n)是 (n) 。再次设c（0）为常数，如果取n0=12/c.那么，对于n n0，可得 12n2+6n 12n2 cn因此，f(n)是 (n)渐近分析记号在等式和不等式中的意义vf(n)= (g(n)的确切意义是：f(n) (g(n)。v一般情况下，等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。v例如：2n2 + 3n + 1 = 2n2 + (n) 表示v 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某个函数。v等式和不等式中渐近记号O,o, 和的意义是类似的。渐近分析中函数比较vf(n)= O(g(n) a b;vf(n)= (g(n) a b;vf(n)= (g(n) a = b;vf(n)= o(g(n) a b.5. 渐近分析记号的若干性质v（1）传递性：vf(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；vf(n)= O(g(n)， g(n)= O (h(n) f(n)= O (h(n)；vf(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；vf(n)= o(g(n)， g(n)= o(h(n) f(n)= o(h(n)；vf(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；渐近分析记号的若干性质v（2）反身性：vf(n)= (f(n)；vf(n)= O(f(n)；vf(n)= (f(n).渐近分析记号的若干性质v（3）对称性：vf(n)= (g(n) g(n)= (f(n) .v（4）互对称性：vf(n)= O(g(n) g(n)= (f(n) ；vf(n)= o(g(n) g(n)= (f(n) ；渐近分析记号的若干性质v（5）算术运算：vO(f(n)+O(g(n) = O(maxf(n),g(n) ；vO(f(n)+O(g(n) = O(f(n)+g(n) ；vO(f(n)*O(g(n) = O(f(n)*g(n) ；vO(cf(n) = O(f(n) ；vg(n)= O(f(n) O(f(n)+O(g(n) = O(f(n) 。6. 算法渐近复杂性分析中常用函数v（1）单调函数v单调递增：m n f(m) f(n) ;v单调递减：m n f(m) f(n);v严格单调递增：m f(n).v（2）取整函数v x ：不大于x的最大整数；v x ：不小于x的最小整数。 v（3）多项式函数v p(n)= a0+a1n+a2n2+adnd； ad0;v p(n) = (nd);v f(n) = O(nk) f(n)多项式有界；v f(n) = O(1) f(n) c;v k d p(n) = O(nk) ;vk d p(n) = (nk) ;vk d p(n) = o(nk) ;vk 0:v a0=1;v a1=a ;v a-1=1/a ;v (am)n = amn ; v(am)n = (an)m ; v aman = am+n ;v a1 an为单调递增函数;v a1 nb = o(an)vex 1+x;v|x| 1 1+x ex 1+x+x2 ;v ex = 1+x+ (x2), as x0;（5）对数函数v log n = log2n;v lg n = log10n;v ln n = logen;v logkn = (log n)kl;v log log n = log(log n);v for a0,b0,c0（5）对数函数v|x| 1 vfor x -1,vfor any a 0, , logbn = o(na)（5）对数函数v（6）阶层函数vStirlings approximation （6）阶层函数7. 算法分析中常见的复杂性函数8. 小规模数据9. 中等规模数据二. 算法分析方法v例1-8：顺序搜索算法templateint seqSearch(Type *a, int n, Type k)for (int i=0;i+= 15)2(217)(2nnnTnnT)(10310)212(57257)(222 12102 nOnnnnnnnnTkkii=-=-+=+=-=222 112222225)2(52)2(52) 1 (25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+=+=+=+=-L递归算法复杂性分析例1-9 vint factorial (int n)v v if (n = 0) return 1; v return n*factorial(n-1);v 递归算法复杂性分析v 用展开法求解v T(n)=T(n-1)+1v =(T(n-2)+1)+1=T(n-2)+2v =(T(n-3)+1)+2=T(n-3)+3v v =(T(n-n)+1)+(n-1)=T(0)+n=nv所以，递归算法复杂性分析例1-10 template int Bina