算法复杂性分析

1、数据结构数据结构第二讲第二讲 计算复杂性计算复杂性2.2 算法复杂性分析算法复杂性分析清华大学清华大学 自动化系自动化系 黄双喜黄双喜 博士博士How many Algorithms we have?How many Algorithms we have? 冒泡排序、插入排序、桶排序、计数排序、冒泡排序、插入排序、桶排序、计数排序、归并排序、基数排序、希尔排序、归并排序、基数排序、希尔排序、堆排序堆排序、快速排序快速排序排序算法排序算法 顺序查找、折半查找、二叉树查找、顺序查找、折半查找、二叉树查找、索引查找、散列查找索引查找、散列查找搜索算法搜索算法 广度广度/深度优先算法、最小生成树算法深

2、度优先算法、最小生成树算法、最短路径算法、最大流算法最短路径算法、最大流算法图算法图算法 矩阵运算、矩阵运算、方程求解、方程求解、优化算法、优化算法、- 其他How much do you know about algorithmsHow much do you know about algorithms怎么想到的？怎么想到的？怎么设计出来的？怎么设计出来的？给你一个新问题，能设计出算法吗？给你一个新问题，能设计出算法吗？怎么去设计一个算法呢？怎么去设计一个算法呢？怎么去设计一个优秀的算法呢？怎么去设计一个优秀的算法呢？算法分析与设计能力算法复杂性理论本讲提纲本讲提纲算法有好坏之算法有好坏之份

3、吗？如何理份吗？如何理解算法之美？解算法之美？高性能计算高性能计算机可以弥补机可以弥补算法问题吗？算法问题吗？如何评价算如何评价算法的好坏？法的好坏？好有多好？好有多好？差有多差？差有多差？v算法复杂性概念与定义算法复杂性概念与定义v算法复杂性的阶及大O表示法v算法复杂性分析方法算法有好坏之分吗？v算法的好与坏 高斯的故事1+2+3+4+5+6+100 = ?（1+100）+（2+99）+（50+51）= 50101 （高斯算法）高斯：高斯：“给我最大快乐的，不是已懂得知识，而是不断的学给我最大快乐的，不是已懂得知识，而是不断的学习；不是已有的东西，习；不是已有的东西， 而是不断的获取；不是已

4、达到的高度，而是不断的获取；不是已达到的高度，而是继续不断的攀登。而是继续不断的攀登。 ”高斯（数学王子）高斯（数学王子）11请大家设计一个算法，求解斐波那契数列第请大家设计一个算法，求解斐波那契数列第n项的值。项的值。v斐波那契数列问题兔子数列兔子数列（1）递归算法 if(n = 1| n= 2) return 1; else return fib(n -1) + fib(n -2); int fib(n) （2）迭代算法 算法之美？算法之美？int fib(n) int i,f1=1,f2=1,f3; if(n=1|n=2) printf (1); else for(i=0;in- 2;i

5、+) f3=f1+f2; /f1 f2表示当前的值 f1=f2; f2=f3; return f3 (100)354224848179261915075F递归次数：递归次数：2Fib(n)-1 (为什么？为什么？) （1）递归算法 if(n = 1| n= 2) return 1; else return fib(n - 1) + fib(n - 2); int fib(n) （2）迭代算法迭代次数：迭代次数： n-2次次int f(n) int i,f1=1,f2=1,f3; if(n=1|n=2) printf (1); else for(i=0;in- 2;i+) f3=f1+f2; /

6、f1 f2表示当前的值 f1=f2; f2=f3; return f3 v百钱百鸡问题百钱百鸡问题 中国古代数学家张丘建在他的算经中提出了他的著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？算法二算法二算法一算法一计算机能解决算法问题吗？ 问题：问题：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短（每个城市只经过一次）？ 枚举算法：枚举算法：n个城市的一个排列表示商人按这个排列顺序推销并返回起点。旅行商问题（TSP） 固定一个城市为起终点，则需要(n-1)!次

7、枚举。若用一台每秒可运算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？）？）如何评价算法好与坏？能否直接在计算机上运行算法，通过记录运算时间来评判算法好坏呢？计算机硬件环境影响算法的评判。我们评的是算法，不是计算机速度。就是不同计算机上运

8、行，同一个算法的复杂度应该是一样的。一个算法常常是针对一个问题来设计的，但同一问题规模不同时计算时间也不一样。算 法 的 本 质 特 性是 什 么？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时算法所需的空间

9、资源为S(N,I) ，S(N,I)称为算法的空间复杂性。算法空间复杂性算法分析：分析算法复杂性的过程；算法分析：分析算法复杂性的过程；时间复杂性的最好、最坏及平均情况分析考虑三种情况：考虑三种情况：最坏情况最坏情况、最好情况最好情况和和平均情况平均情况 Tmax(N) Tmin(N) Tavg(N) ),(),(),(max),(max)(*11maxINTINetINetINTNTkiiikiiiDIDINN),(),(),(min),(min)(11minINTINetINetINTNTkiiikiiiDIDINN),()(),()()(1INetIPINTIPNTkiiiDIDIavgN

10、N精确计数精确计数和分析难和分析难度大！度大！本讲提纲本讲提纲v算法复杂性概念与定义v算法复杂性的阶及大算法复杂性的阶及大O表示法表示法v算法复杂性分析方法算法复杂性的渐近性态 算法复杂性的渐近性态：对于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 ) 时间复杂性渐进表示法v 定义定义1：如果存在两个正常数c和n0，对于所有的nn0，有:f(n)cg(n)， 则记作：f(n) =

11、(g(n)v 定义定义2：如果存在两个正常数c和n0，对于所有的nn0，f(n) cg(n)，则记作： f(n) = (g(n)v 定义定义3：如果存在正常数c1，c2和n0，对于所有的nn0，有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!): 求

12、具有N个元素的全排列的算法 O(1)O(logn)O(n) O(nlogn) O(n2)O(2n)O(n!)本讲提纲本讲提纲v算法复杂性概念与定义v算法复杂性的渐进性态及大O表示法v算法复杂性分析方法算法复杂性分析方法 空间复杂性分析方法 时间复杂性分析方法空间复杂性分析方法v空间复杂性：问题实例所有参数所占据的存储空间之和。在二进制编码条件下，任意正整数x占用位数为：考虑一个符号位和一个数据分隔位，任何一个整数x的输入规模为：【例例】TSPTSP实例规模的计算实例规模的计算 对于TSP问题，它的任何一个实例由城市数n和城市间的距离D确定。 TSP的任何一个实例I的规模（考虑符号和数据分隔位）

13、为 ：O(?)时间复杂性分析方法估算算法运行时间的方法迭代计数：计算循环的迭代次数迭代计数：计算循环的迭代次数操作计数：找出关键操作，确定操作计数：找出关键操作，确定这些关键操作所需要的执行次数这些关键操作所需要的执行次数常用的级数公式及复杂度【例：多重循环算法记数】x=1;for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k1) 5. i = i / 2;6. for (j=0;ji;j+) 7. if (comp(groupj+i,groupj)8. groupj = groupj+i;9. 10. return group0;11. 1( )224kjjnn

14、nnT nn)214121(kn)211(kn1n分析分析comp(groupj+i,groupj)的的运行次数运行次数O(n)【例：随机洗牌算法】输入：输入：牌A,牌的张数n输出：输出：洗牌后的牌A1. template 2. void shuffle(Type A,int n)3. 4. int i,k,m,d;5. random_seed(0);6. for (k=1;k=n;k+) 7. m = n / k ;8. for (i=1;i 1)(1)(ncnbnaTncnTk kkkbkkabanObannObanOnTb)()log()()(log通用递推式：通用递推式：大师解法大师解

15、法：大师解法思路大师解法思路log1log1223322loglog1log122log0log0( )(/ )( )(/)(/ )( )(/)(/)(/ )( )(1)(/).(/)(/ )( )(1)(/)()(/)bbbnbbnbbnnnajjjajjjT naT n bf na T n baf n bf na T n ba T n baf n bf naTaf n ba T n baf n bf nnTa f n bna f n b logloglog1( )()2( )()3( )()bbbaaaf nnf nnf nn 、渐进增长趋势(*f(n)=cnk)【例：解递推式 T(n)=

16、 4 T(n/2)+n】解： a=4 b=2 c=1 k=1 且 a=4 bk=21=2 anOb)(log nT)( 2nO)(【例：解递推式 T(n)= 4 T(n/2)+n2】解： a=4 b=2 c=1 k=2 且 a=4 bk=22=4 nT)(bknnO)log( 22nnO)log(【例：解递推式 T(n)= 4 T(n/2)+n3】解： a=4 b=2 c=1 k=3 且 a=4 bk=23=8 nT)(knO)( 3nO)(小节小节43v 算法复杂性定义算法复杂性定义v 时间复杂性：需要时间资源的量时间复杂性：需要时间资源的量v 空间复杂性：需要的空间资源的量空间复杂性：需要的空间资源的量v 算法复杂性表示方法算法复杂性表示方法v 算法复杂性渐进性态算法复杂性渐进性态v 算法复杂性大算法复杂性大O表示法表示法v 算法复杂性分析过程与方法算法复杂性分析过程与方法 （1）分析问题规模及算法的循环及递归情况）分析问题规模及算法的循环及递归情况 （2）求出累计和函数）求出累计和函数T(n)、S(n) （3