第2章算法分析.

第2章算法分析基础学习要点:理解算法分析的任务和目的掌握渐近标记法在算法分析中的应用掌握算法分析的方法能够分析算法的最好、最坏、平均时间复杂度算法分析的任务：对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的评价有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少，即算法运行的时间和空间效率。目的：设计和选择出复杂性尽可能低的算法来解决问题。★2.1.1时间复杂性算法运行所需要时间资源的量，T=T(n,I,A)。其中，n表示算法要解的问题的规模；I表示算法的输入；A表示算法本身。算法在一台抽象计算机上运行的时间。T(n,I)=其中，ti是计算机所提供的元运算执行一次所需时间；ei是算法用到元运算Oi的次数。2.1算法的复杂性kiiiInet1),(三种情况下的时间复杂性最坏情况Tmax(n)=max{T(I)|size(I)=n}最好情况Tmin(n)=min{T(I)|size(I)=n}平均情况Tavg(n)=其中，I是问题的规模为n的实例，p(I)是实例I出现的概率。NIsizeITIp)()()(2.1.2空间复杂性算法运行所需要空间资源的量，S=S(n,I,A)。其中，n表示算法要解的问题的规模；I表示算法的输入；A表示算法本身。算法在一台抽象计算机上运行时所占用的空间。分析起来比时间复杂性简单，本课程以时间复杂性为讨论主体。2.1.3渐近复杂性对于T(n)，如果存在f(n)，使得当n→∞时有(T(n)-f(n))/T(n)→0，那么，就说f(n)是T(n)当n→∞时的渐近性态。又称算法A的渐近复杂性。在数学上，f(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。例如，T(n)＝3n2+4nlogn+7，则f(n)的一个答案是3n2，因为，此时有(T(n)-f(n))/T(n)=→0（当n→∞）渐近复杂性分析只关心f(n)的阶！7log437log42nnnnn2.2.1评价算法的准则算法正确性算法结构（健壮性）最佳性时间复杂性空间复杂性2.2算法分析的一般方法2.2.2评价算法时间复杂性的一般方法分析并确定：算法的哪些参数决定算法的“输入规模”？原因：问题实例的输入规模较大的，算法得到输出需要更多的时间开销。明确：被分析算法的“关键操作”是什么？关键操作：算法中重要的操作，或所关心的操作。“关键操作的数量”→“算法的时间复杂度”！例：内排：(“比较类”)待排序元素之间的“比较”次数；待排序元素的“移动”次数。查找：待查找值x与数据元素之间的“比较”次数。矩阵乘法：矩阵元之间的乘法/加法运算次数。算法分析的目标：考察算法的“关键操作”数，随“问题规模”而变化的规律。nt(n)12345123450nnlogn2nn5提高计算速度对不同时间复杂性函数的影响对比T(n)微秒lognnnlognn2n3n52n3nn!n=103.310331001毫秒0.1秒1毫秒59毫秒3.6秒n=405.340213160064毫秒1.7分12.7天3855世纪103世纪n=605.9603543600216毫秒1.3分366世纪1.3×1013世纪1066世纪多项式函数指数函数时间复杂性函数用现在的计算机用快100倍的计算机用快1000倍的计算机nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29算法时间复杂度的渐近表示算法的时间开销随问题规模增大的变化趋势。例2-1：简单选择排序算法的“比较”次数0123456…n-1a:(2,5,8,|12,9,20,15,…,66)||↑↑小大ij(K)voidSELECT_SORT(Typea[],intn){FOR(inti=0;i=n-2;i++){intk=i;FOR(intj=i+1;j=n-1;j++){IF(a[j]a[k])k=j;};IF(k!=i)a[k]⇔a[i];};}T(n)===n(n-1)/2→t(n)20111ninij201niin注：n个元素存放在a[0]～a[n-1]之上！?多项式函数2.2.3算法渐近复杂性分析定义界函数设：f和g是两个函数，f,g:N→R+。若存在正整数c和n0，使得对于所有n≥n0,都有：f(n)≤cg(n)，则称g(n)是f(n)的上界，记为：f(n)=O(g(n))理解：ⅰ能够满足定义的g(n)，可以是一个函数集合ⅱg(n)不小于f(n)，且g(n)是“简洁”的函数。例如，当n≥10时，有2n2+11n-10≤3n2，所以有2n2+11n-10=O(n2)O标记的运算规则：⑴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))若存在正整数c和n0，使得对于所有n≥n0，都有：f(n)≥cg(n)，则称g(n)是f(n)的下界，记为：f(n)=Ω(g(n))若存在正整数c1、c2和n0，使得对于所有n≥n0，都有：c1g(n)≤f(n)≤c2g(n)，则称g(n)是f(n)的精确界，记为：f(n)=Θ(g(n))如果对于任意c＞0，都存在非负整数n0，使得当n≥n0时，有f(n)＜cg(n)，则称g(n)是f(n)的非紧上界，记为：f(n)=o(g(n))如果对于任意c0，都存在正数n00，使得当n≥n0时，有：f(n)＞cg(n)，则称g(n)是f(n)的非紧下界，记为：f(n)=(g(n))定理1：(g(n))=O(g(n))(g(n))常用函数单调函数单调递增：mnf(m)f(n)单调递减：mnf(m)f(n)严格单调递增：mnf(m)f(n)严格单调递减：mnf(m)f(n)取整函数x：不大于x的最大整数x：不小于x的最小整数多项式函数如果p(n)=a0+a1n+a2n2+…+adnd，ad0；则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);kdp(n)=o(nk);kdp(n)=(nk)指数函数对于正整数m,n和实数a0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman=am+n;a1an为单调递增函数;a1nb=o(an)0limnbnan032!!3!21iixixxxxeex1+x|x|11+xex1+x+x2∴当x0，有ex=1+x+(x2)xnnenx1lim对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=(logn)kl;loglogn=log(logn);如果a0,b0,c0，则abbalogbaabcccloglog)(loganabnbloglogbaaccblogloglogaabblog)/1(logbaablog1logacbbcaloglog阶乘函数Stirling’sapproximation(斯特林逼近公式)：其中，00)!1(1!nnnnnnn321!nennnn11π2!neennnnπ2!nnn121α1121)(!nnon)2(!nn)log()!log(nnn例2-2：分析“计算n阶方阵A、B的乘积”算法。voidMatrixMulti(TypeA[],TypeB[],TypeC[],intn){FOR(inti=0;i=n-1;i++){FOR(intj=0;j=n-1;j++){C[i,j]=0;FOR(intk=0;k=n-1;k++)C[i,j]=C[i,j]+A[i,k]*B[k,j];};};}T(n)====n3=(n3)1010101ninjnk1010ninjn102nin算法的最坏情况下的复杂度设：I是问题规模为n的所有输入的集合，i∈I是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。则，算法A的最坏情况复杂度：WA(n)=max{ti(n)}i∈I例2-3：“顺序表查找”算法intSearch_line(Typea[],intn,Typex){a[n]=x;intj=0;WHILE(x!=a[j])j=j+1;IF(j==n)RETURN(0);失败ELSERETURN(1);}失败查找最坏特性：WAu(n)=n+1平均复杂度设：I是问题规模为n的所有输入的集合，i∈I是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。Pi(n)是输入i出现在I中的概率。则，算法A的平均时间复杂度：AVA(n)=∑(Pi(n)ti(n))i∈I例2-4：“顺序表查找”算法的平均复杂度：设：“失败”概率为q(0≤q≤1)。而且假设“成功”查找时，各种输入“等概率”，即：成功查找的输入概率为psi(n)=(1-q)/nAVA(n)=∑Pi(n)ti(n)=∑Psi(n)ti(n)+∑Pui(n)ti(n)=∑[(1-q)/n·(j+1)]+q·(n+1)=(1-q)/n∑(j+1)+q(n+1)=(1+q)(1+n)/2i∈Isi∈I成功ui∈I失败n-1j=0n-1j=0课后作业P28：1.2.2.4算法分析实例非递归算法分析仅依赖于“问题规模”的时间复杂度例2-5：交换i和j的内容。Temp=i;i=j;j=Temp;以上三条基本语句的执行次数(语句频度)均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。结论：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。例2-6：变量计数之一。(1)x=0；y=0；(2)for(k=1;k=n;k++)(3)x++；(4)for(i=1;i=n;i++)(5)for(j=1;j=n;j++)(6)y++；该算法段的时间复杂度为T(n)=O(n2)。结论：当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。T(n)==n+n2ninjnk11111n＞1时，有T(n)≤2n2=t(n)(n0=1，c=2)Tx(n)+Ty(n)=例2-7：变量计数之二。(1)x=1;(2)for(i=1;i=n;i++)(3)for(j=1;j=i;j++)(4)for(k=1;k=j;k++)(5)x++;该算法段的基本语句是(5)，从内层循环向外层分析语句(5)的执行次数：===niijjk1111niijj11ninnnnnii12/]2/)1(6/)12)(1([2/)1(则，该算法的时间复杂度为：T(n)=O(n3/6+低次项)=O(n3)62323nnn算法的时间复杂度与输入实例的初始状态有关例2-8：一个简单k-选择算法(伪码)如下所示。算法思想：首先采用冒泡排序算法，按照从小到大次序，排出a数组的前k个元素，然后返回a数组的第k-1个元素。