算法复杂性分析

数据结构第二讲计算复杂性2.2算法复杂性分析清华大学自动化系黄双喜博士[e-mail]e?•冒泡排序、插入排序、桶排序、计数排序、归并排序、基数排序、希尔排序、堆排序、快速排序排序算法•顺序查找、折半查找、二叉树查找、索引查找、散列查找搜索算法•广度/深度优先算法、最小生成树算法、最短路径算法、最大流算法图算法•矩阵运算、方程求解、优化算法、--------其他数据结构—计算复杂性分析Howmuchdoyouknowaboutalgorithms怎么想到的？怎么设计出来的？给你一个新问题，能设计出算法吗？怎么去设计一个算法呢？怎么去设计一个优秀的算法呢？？？？？？算法分析与设计能力算法复杂性理论数据结构—计算复杂性分析本讲提纲算法有好坏之份吗？如何理解算法之美？高性能计算机可以弥补算法问题吗？如何评价算法的好坏？好有多好？差有多差？算法复杂性概念与定义算法复杂性的阶及大O表示法算法复杂性分析方法数据结构—计算复杂性分析算法有好坏之分吗？算法的好与坏高斯的故事1+2+3+4+5+6+……+100=?（1+100）+（2+99）……+（50+51）=50×101（高斯算法）高斯：“给我最大快乐的，不是已懂得知识，而是不断的学习；不是已有的东西，而是不断的获取；不是已达到的高度，而是继续不断的攀登。”高斯（数学王子）数据结构—计算复杂性分析11请大家设计一个算法，求解斐波那契数列第n项的值。斐波那契数列问题数据结构—计算复杂性分析兔子数列（1）递归算法if(n==1||n==2){return1;}else{returnfib(n-1)+fib(n-2);}}intfib(n){数据结构—计算复杂性分析（2）迭代算法算法之美？intfib(n){inti,f1=1,f2=1,f3;if(n==1||n==2){printf(1);}else{for(i=0;in-2;i++){f3=f1+f2;//f1f2表示当前的值f1=f2;f2=f3;}returnf3}数据结构—计算复杂性分析(100)354224848179261915075F递归次数：2Fib(n)-1(为什么？)（1）递归算法if(n==1||n==2){return1;}else{returnfib(n-1)+fib(n-2);}}intfib(n){（2）迭代算法迭代次数：n-2次数据结构—计算复杂性分析intf(n){inti,f1=1,f2=1,f3;if(n==1||n==2){printf(1);}else{for(i=0;in-2;i++){f3=f1+f2;//f1f2表示当前的值f1=f2;f2=f3;}returnf3}百钱百鸡问题中国古代数学家张丘建在他的《算经》中提出了他的著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？算法二算法一计算机能解决算法问题吗？•问题：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短（每个城市只经过一次）？•枚举算法：n个城市的一个排列表示商人按这个排列顺序推销并返回起点。旅行商问题（TSP）数据结构—计算复杂性分析•固定一个城市为起终点，则需要(n-1)!次枚举。若用一台每秒可运算40亿次（40*108）的计算机来计算，完成15个城市枚举需要325秒，18个城市就已经变成23天，计算20个城市的时间我们已经不能忍耐：190年！！！旅行商问题（TSP）Nn!运算时间136.2*109约1秒151.3*1012约325秒186.4*1015约23天202.41018约190年数据结构—计算复杂性分析*兴趣阅读：克雷数学研究所的世界七大数学难题（P=NP？）如何评价算法好与坏？能否直接在计算机上运行算法，通过记录运算时间来评判算法好坏呢？计算机硬件环境影响算法的评判。我们评的是算法，不是计算机速度。就是不同计算机上运行，同一个算法的复杂度应该是一样的。一个算法常常是针对一个问题来设计的，但同一问题规模不同时计算时间也不一样。算法的本质特性是什么？数据结构—计算复杂性分析T=T(N,I)：时间复杂性S=S(N,I)：空间复杂性算法复杂性定义•度量算法计算难度的一种尺度，反映了算法消耗的资源情况。用N、I来表示算法要解决问题的规模和算法的输入，用C表示算法的复杂性，有：C=F(N,I)算法复杂性•如果问题的规模为n，在算法输入为I时算法所需的时间资源为T(N,I)，T(N,I)称为算法的时间复杂性。算法时间复杂性•如果问题的规模为n，在算法输入为I时算法所需的空间资源为S(N,I)，S(N,I)称为算法的空间复杂性。算法空间复杂性算法分析：分析算法复杂性的过程；数据结构—计算复杂性分析时间复杂性的最好、最坏及平均情况分析考虑三种情况：最坏情况、最好情况和平均情况Tmax(N)Tmin(N)Tavg(N)),(),(),(max),(max)(**11maxINTINetINetINTNTkiiikiiiDIDINN),(),(),(min),(min)(~~11minINTINetINetINTNTkiiikiiiDIDINN),()(),()()(1INetIPINTIPNTkiiiDIDIavgNN精确计数和分析难度大！数据结构—计算复杂性分析本讲提纲算法复杂性概念与定义算法复杂性的阶及大O表示法算法复杂性分析方法数据结构—计算复杂性分析算法复杂性的渐近性态算法复杂性的渐近性态：对于F(N)，如果存在F’(N)，使得当N→∞时有：(F(N)-F’(N))/F(N)→0我们说F’(N)是F(N)当N→∞时的渐近性态例：F(N)=3N2+4Nlog2N+7，求F’(N)F’(N)的一个答案是3N2，因为这时有：(F(N)-F’(N))/F(N)数据结构—计算复杂性分析时间复杂性渐进表示法定义1：如果存在两个正常数c和n0，对于所有的n≥n0，有:f(n)≤cg(n)，则记作：f(n)=Ο(g(n))定义2：如果存在两个正常数c和n0，对于所有的n≥n0，f(n)≥cg(n)，则记作：f(n)=Ω(g(n))定义3：如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1g(n)≤f(n)≤c2g(n)，则记作：f(n)=(g(n))数据结构—计算复杂性分析常见的算法复杂度的大O阶O(1):表示算法的运行时间为常量O(logn):二分搜索算法O(n):表示该算法是线性算法O(nlogn):快速排序算法O(n2):对数组进行排序的简单算法，如直接插入排序算法。O(n3):做两个n阶矩阵的乘法运算O(2n):求具有n个元素集合的所有子集的算法O(n!):求具有N个元素的全排列的算法O(1)O(logn)O(n)O(nlogn)O(n2)O(2n)O(n!)数据结构—计算复杂性分析本讲提纲算法复杂性概念与定义算法复杂性的渐进性态及大O表示法算法复杂性分析方法空间复杂性分析方法时间复杂性分析方法数据结构—计算复杂性分析空间复杂性分析方法空间复杂性：问题实例所有参数所占据的存储空间之和。在二进制编码条件下，任意正整数x占用位数为：考虑一个符号位和一个数据分隔位，任何一个整数x的输入规模为：数据结构—计算复杂性分析【例】TSP实例规模的计算对于TSP问题，它的任何一个实例由城市数n和城市间的距离D确定。TSP的任何一个实例I的规模（考虑符号和数据分隔位）为：O(?)数据结构—计算复杂性分析时间复杂性分析方法估算算法运行时间的方法迭代计数：计算循环的迭代次数操作计数：找出关键操作，确定这些关键操作所需要的执行次数数据结构—计算复杂性分析常用的级数公式及复杂度数据结构—计算复杂性分析【例：多重循环算法记数】x=1;for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=j;k++)x++;分析x++运行次数：2/]2/)1(6/)12)(1([2/)1(1)(111111nnnnniijNTniijjkniniijO(n3)数据结构—计算复杂性分析【例：竞技淘汰算法记数】输入：选手成员group[],选手个数n(n=2k)输出：冠军的选手1.Typegame(Typegroup[],intn)2.{3.intj,i=n;4.while(i1){5.i=i/2;6.for(j=0;ji;j++)7.if(comp(group[j+i],group[j]))8.group[j]=group[j+i];9.}10.returngroup[0];11.}1()224kjjnnnnTnn)214121(kn)211(kn1n分析comp(group[j+i],group[j])的运行次数O(n)数据结构—计算复杂性分析【例：随机洗牌算法】输入：牌A[],牌的张数n输出：洗牌后的牌A[]1.templateclassType2.voidshuffle(TypeA[],intn)3.{4.inti,k,m,d;5.random_seed(0);6.for(k=1;k=n;k++){7.m=n/k;8.for(i=1;i=m;i++){9.d=random(1,n);10.swap(A[i],A[d]);11.}12.}13.}第8行开始的内部for循环的循环体，其执行次数依次为：,/2,/3,/nnnnn11()/1/nniiTnnini分析swap(A[i],A[d])运行次数O(nlogn)数据结构—计算复杂性分析递归算法的时间复杂性分析当一个算法包含对自身的递归调用时，称为递归算法。其运行时间通常用递归方程来表示。方程的解即为该函数的复杂度。数据结构—计算复杂性分析递归方程常见形式：1）规模等差递减型T(n)=a×T(n-1)+[b×T(n-2)]或者T(n)=a×T(n-1)+[b×T(n-2)]+f(n)2）规模等比递减型T(n)=a×T(n/b)+[b×T(n/c)]或者T(n)=a×T(n/b)+[b×T(n/c)]+f(n)（1）递归树法2)2(2)(nnTnT求解：数据结构—计算复杂性分析迭代2次可以得：22()2(2()())42nnTnTn继续迭代，将其完全展开可得：T(n)=n2+2((n/2)2+2((n/22)2+2((n/23)2+2((n/24)2+…+2((n/2i-1)2+2T(n/2i)))…))))当n/2i==1时，迭代结束（1）递归树法2)2(2)(nnTnT求解：222222222241)4()4()4()4(21)2()2(nnnnnnnnnn共logn层2()(11/21/41/8.....)TnnO（n2）T(1)T(1)T(1)T(1)2log2n数据结构—计算复杂性分析递归树给出一个递归算法执行过程的成本模型（1）递归树法求解：数据结构—计算复杂性分析T(n)=T(n/3)+T(2n/3)+n当(2/3)kn==1时，迭代结束（2）递归方程法（课外了解）标准形式：k阶0,...,,,,0)()2()1()(2121kkkaaaaknknHanHanHanH是常数，求解步骤：（1）求出特征方程的k个根（2）如果没有重根，则该递推方程的通解为0...11kkkaxax待定常数knkknnCCCqCqCqCnH,...,,...)(212211如果有重根，如果q是e重特征根，通解对应于根q的部分为neeqnCnCC)...(121整个通解为各个不等的特征根的对应部分之和（3）代入初值确定待定常数。常系数线性齐次递推方程的求解数据结构—