计算机算法设计与分析（第4版）第1章算法概述算法(Algorithm)程序(Program)问题求解(ProblemSolving)算法复杂性分析算法的时间复杂性算法渐近复杂性渐近分析的记号（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))渐近分析记号在等式和不等式中的意义渐近分析中函数比较渐近分析记号的若干性质（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)}).算法渐近复杂性分析中常用函数取整函数的若干性质（3）多项式函数p(n)=a0+a1n+a2n2+…+adnd；ad>0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;kdp(n)=O(nk);kdp(n)=(nk);k>dp(n)=o(nk);k<dp(n)=(nk).（4）指数函数对于正整数m,n和实数a>0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman=am+n;a>1an为单调递增函数;a>1nb=o(an)ex1+x;|x|11+xex1+x+x2;ex=1+x+(x2),asx0;（5）对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=(logn)kl;loglogn=log(logn);fora>0,b>0,c>0|x|1forx>-1,foranya>0,,logbn=o(na)（6）阶层函数Stirling’sapproximation算法分析中常见的复杂性函数小规模数据中等规模数据用C++描述算法（1）选择语句：（1.1)if语句：（1.2)？语句：（1.3)switch语句：（2）迭代语句：（3）跳转语句：（4）函数：（5）模板template：（6）动态存储分配：（6.2）一维数组：（6.3）运算符delete：（6.4）动态二维数组：当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。算法分析方法（1）Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p(0p1)；(b)在数组的每个位置i(0i<n)搜索成功的概率相同，均为p/n。算法分析的基本法则template<c