算法设计与分析算法分析基础.pptx

第第2章章 算法分析基础算法分析基础2.2 算法的渐进分析算法的渐进分析2.3 最好、最坏和平均情况最好、最坏和平均情况2.4 非递归算法的分析非递归算法的分析2.5 递归算法的分析递归算法的分析2.1 算法分析的基本概念算法分析的基本概念2.1 算法分析的基本概念算法分析的基本概念 一、算法分析（一、算法分析（Algorithm Analysis）：对算法所需要的两种计）：对算法所需要的两种计算机资源算机资源时间和空间进行估算时间和空间进行估算 时间复杂性（时间复杂性（Time Complexity）空间复杂性（空间复杂性（Space Complexity）二、算法分析的目的：二、算法分析的目的：设计算法设计算法设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者三、算法分析的两个阶段三、算法分析的两个阶段 1 1、事前分析事前分析求出该算法的一个时间限界函数。求出该算法的一个时间限界函数。2 2、事后测试事后测试收集此算法的执行时间和实际占用空间的收集此算法的执行时间和实际占用空间的统计资料。统计资料。2.1 算法分析的基本概念算法分析的基本概念 2.2 算法的渐进分析算法的渐进分析一、相关概念一、相关概念l算法的渐进分析算法的渐进分析 是一种事前估算的方法，是指忽略具体机器、编程语言和编译是一种事前估算的方法，是指忽略具体机器、编程语言和编译器的影响，器的影响，只关注在输入规模增大时算法运行时间的增长趋势只关注在输入规模增大时算法运行时间的增长趋势。l渐进时间复杂性渐进时间复杂性 当问题的规模当问题的规模n趋向无穷大时，影响算法效率的重要因素是趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而的数量级，而其他因素仅是使时间复杂度相差常数倍其他因素仅是使时间复杂度相差常数倍，因此，因此，可可以用以用T(n)的数量级的数量级(阶阶)评价算法。时间复杂度评价算法。时间复杂度T(n)的数量级的数量级(阶阶)称称为渐进时间复杂性。为渐进时间复杂性。确定一个算法时间的数量级是十分重要的，它在本质上反映了确定一个算法时间的数量级是十分重要的，它在本质上反映了确定一个算法时间的数量级是十分重要的，它在本质上反映了确定一个算法时间的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。一个算法所需要的计算时间。一个算法所需要的计算时间。一个算法所需要的计算时间。l语句频度：语句频度：语句执行的语句执行的次数次数l算法的语句频度算法的语句频度f(n)：f(n)=(语句语句(i)的执行次数的执行次数）算法中基本操作重复执行的次数之和算法中基本操作重复执行的次数之和l算法算法的的执行时间：是执行时间：是所有语句的执行时间之和所有语句的执行时间之和 T（n）=(语句语句(i)的执行次数的执行次数语句的执行时间语句的执行时间 )(假设每条语句执行的时间相等假设每条语句执行的时间相等)l渐进时间复杂度表示：渐进时间复杂度表示：随着问题规模随着问题规模 n 的增长，算法执行时间的增长率和算法的语句频的增长，算法执行时间的增长率和算法的语句频度度f（n）的增长率相同，则可记作：）的增长率相同，则可记作：T（n）=O（f（n）称称 T（n）为算法的）为算法的(渐近渐近)时间复杂度时间复杂度2.2 算法的渐进分析算法的渐进分析2.2 算法的渐进分析算法的渐进分析二、表示方法二、表示方法 1.大大O符号符号-运行时间的上界运行时间的上界l定义定义1.1 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都，都有有T(n)cf(n)，则称，则称T(n)=O(f(n)n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况况无无关关紧要紧要T(n)cf(n)大大O符号描述增长率的上限，表示符号描述增长率的上限，表示T(n)的增长的增长最多最多像像f(n)增长增长的那样快的那样快当说一个算法具有当说一个算法具有O(f(n)的计算时间时，指的是如果此算法的计算时间时，指的是如果此算法用用n值不变的同一类数据在某台机器上运行时，所用的时间值不变的同一类数据在某台机器上运行时，所用的时间总是小于总是小于f(n)的一个常数倍。的一个常数倍。所以所以f(n)是计算时间是计算时间T(n)的一个的一个上界函数，上界函数，T(n)的数量级就是的数量级就是f(n)典型的增长阶典型的增长阶:O(1),O(lgn),O(n),O(nlgn),O(n2),O(n3),O(2n),O(n!)2.2 算法的渐进分析算法的渐进分析l算术运算：算术运算：O(f(n)+O(g(n)=O(maxf(n),g(n)；O(f(m)+O(g(n)=O(f(m)+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)。若T(n)是关于n的k阶多项式，那么T(n)=O(nk)2.2 算法的渐进分析算法的渐进分析证明：取证明：取n n0 0=1,=1,当当n=nn=n0 0时，利用时，利用T(n)T(n)的定义和一个简单的不等式，的定义和一个简单的不等式，有有取取c=|ac=|am m|+|+.+|a.+|a0 0|定理得证定理得证.事实上，只要将事实上，只要将n n0 0取得足够大，可以证明只要取得足够大，可以证明只要c c是比是比|a|am m|大的任意大的任意一个常数，此定理都成立。一个常数，此定理都成立。定理定理1.1 1.1 若若T(n)=aT(n)=am mn nm m+a+a1 1n+an+a0 0是一个是一个m m次多项式，则次多项式，则T(n)=O(nT(n)=O(nm m)。此定理表明，变量此定理表明，变量n n的固定阶数为的固定阶数为m m的任一多项式，与此多项式的的任一多项式，与此多项式的最高阶最高阶n nm同阶同阶.2.2 算法的渐进分析算法的渐进分析2.2 算法的渐进分析算法的渐进分析l示例2.2 算法的渐进分析算法的渐进分析2.2 算法的渐进分析算法的渐进分析例例.1.1）假设某算法在输入规模是）假设某算法在输入规模是 时为时为 .在某台计算机上在某台计算机上实现并完成该算法的时间是实现并完成该算法的时间是 秒秒.现有另一台计算机现有另一台计算机,其运行速度为第其运行速度为第一台的一台的6464倍倍,那么那么,在这台计算机上用同一算法在在这台计算机上用同一算法在 秒内能解决规模为秒内能解决规模为多大的问题多大的问题?规模语句频度运行时间/每语句总时间关系式关系式:算法语句频度*运行速度运行速度(时间时间/每语句每语句)=)=运行总时间运行总时间解解:设在新机器上设在新机器上 秒内能解决规模为秒内能解决规模为 的问题，的问题，由于新机器运行速度提高由于新机器运行速度提高6464倍，则倍，则运行时间运行时间/每语句变为每语句变为由关系式由关系式，得，得解，得解，得2.2 算法的渐进分析算法的渐进分析由于此时由于此时 ，新机器的运行，新机器的运行速度速度/每语句为：每语句为：2)2)若上述算法改进后，新若上述算法改进后，新算法算法 ,则在新机器上则在新机器上用用 秒秒时间时间能解决输入规模为多大的问题？能解决输入规模为多大的问题？代入关系式代入关系式，得，得设在新机器上用设在新机器上用 t 秒时间能解决输入规模为秒时间能解决输入规模为 N 的问题，则的问题，则解，得解，得2.2 算法的渐进分析算法的渐进分析思考：以上说明了什么问题？2.大大符号符号-运行时间的下界运行时间的下界 l定义定义1.2 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T(n)cg(n)，则称，则称T(n)=(g(n)n0问题规模问题规模n执执行行次次数数n0之之 前前 的的情情况况无无关关紧要紧要T(n)cg(n)2.2 算法的渐进分析算法的渐进分析大大符号用来描述符号用来描述增长率的下界增长率的下界也就是说，也就是说，T(n)=(g(n)是当输入规模为是当输入规模为n时，算法消耗时间的时，算法消耗时间的最小值最小值。与大与大符号对称，这个下限的阶越高，结果就越有价值。符号对称，这个下限的阶越高，结果就越有价值。问题的计算时间下界为问题的计算时间下界为(f(n)，则计算时间复杂性为，则计算时间复杂性为O(f(n)的的算法是最优算法。算法是最优算法。例如：计算时间例如：计算时间复杂性为复杂性为O(nlogn)的排序算法是最优算法的排序算法是最优算法。（堆（堆排序排序算法就是算法就是最优最优算法）。算法）。2.2 算法的渐进分析算法的渐进分析3.符号符号-运行时间的准确界运行时间的准确界 l定义定义1.3 若存在三个正的常数若存在三个正的常数c1、c2和和n0，对于任意，对于任意nn0都都有有c1f(n)T(n)c2f(n)，则称，则称T(n)=(f(n)n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况况无无关关紧要紧要T(n)c2f(n)c1f(n)2.2 算法的渐进分析算法的渐进分析一个算法的一个算法的T(n)=(f(n)意味着该算法在最好和最坏情况下的计算时间意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。就一个常因子范围内而言是相同的。例：例：T(n)5n28n1当当n1时，时，5n28n15n28nn 5n29n5n29n214n2O(n2)当当n1时，时，5n28n15n2(n2)当当n1时，时，14n25n28n15n2 则：则：5n28n1(n2)定理定理1.2 若若T(n)=amnm+am-1nm-1+a1n+a0（am0），），则有则有T(n)=O(nm)且且T(n)=(n m)，因此，有，因此，有T(n)=(n m)。2.2 算法的渐进分析算法的渐进分析【解答解答】当当n1时，时，3n-13nO(n)当当n1时，时，3n-13n-n2n(n)当当n1时，时，3n3n-12n，则，则3n-1(n)例例 T(n)3n-1,求求(?)2.2 算法的渐进分析算法的渐进分析2.3 最好、最坏和平均情况最好、最坏和平均情况 例：例：在一维整型数组在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相等相等的元素（假设该数组中有且仅有一个元素值为的元素（假设该数组中有且仅有一个元素值为k）int Find(int A,int n)for(i=0;in;i+)if(Ai=k)break;return i;（1）最坏情况最坏情况下的时间复杂性 Tmax(n)=max T(I)|size(I)=n（2）最好情况最好情况下的时间复杂性 Tmin(n)=min T(I)|size(I)=n（3）平均情况平均情况下的时间复杂性 Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。2.3 最好、最坏和平均情况最好、最坏和平均情况 2.3 最好、最坏和平均情况最好、最坏和平均情况（1）Tmax(n)=max T(I)|size(I)=n=O(n)（2）Tmin(n)=min T(I)|size(I)=n=O(1)（3）在平均情况下，假设：在数组的每个位置i(0 i n)搜索成功的概率相同，均为 1/n。最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的，通常假设等概率分布通常假设等概率分布结论：如果问题规模相同，时间代价与输入数据有结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。关，则需要分析最好情况、最坏情况、平均情况。2.3 最好、最坏和平均情况最好、最坏和平均情况 1.建立一个代表算法运行时间的建立一个代表算法运行时间的求和表达式求和表达式;2.用用渐进符号渐进符号表示这个求和表达式。表示这个求和表达式。void add()sum=0;for(i=1;i=n;i+)for(j=1;jC);else hanoi(n-1,A,C,B);printf(AC);hanoi(n-1,B,A,C);T(1)=1 (n=1)T(n)=2*T(n-1)+1 (n1)一、递推关系式一、递推关系式一、递推关系式一、递推关系式:用于表示第用于表示第用于表示第用于表示第n n项与它前一项或几项与它前一项或几项与它前一项或几项与它前一项或几项关系项关系项关系项关系的式子。的式子。的式子。的式子。例例:Merge-sort排序算法的复杂性递归方程为排序算法的复杂性递归方程为 T(n)=(1)if n=1 T(n)=2T(n/2)+(n)if n1T(1)=1 (n=1)T(n)=2*T(n-1)+1 (n1)例：例：Hanoi问题问题T(T(n n)=)=？2.5 递归算法的分析递归算法的分析 二、二、建立建立递推关系式递推关系式（关键）关键）对递归算法时间复杂性的分析，关键是根据递归过程，对递归算法时间复杂性的分析，关键是根据递归过程，建立建立递递推推关系式，关系式，然后求解这个递推关系式。然后求解这个递推关系式。步骤：步骤：循环地循环地展开递推关系式，展开递推关系式，把递推关系式转化把递推关系式转化为求和表达式，为求和表达式，然后可使用求和技术解之然后可使用求和技术解之。三、递推关系式的求解三、递推关系式的求解-扩展递归技术扩展递归技术 2.5 递归算法的分析递归算法的分析 +=15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii=-=-+=+=-=222112222225)2(52)2(52)1(25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+=+=+=+=-LL2.5 递归算法的分析递归算法的分析 求以下递推式的时间复杂性求以下递推式的时间复杂性解：设解：设 n=2k2.5 递归算法的分析递归算法的分析 四、通用分治递四、通用分治递推关系式推关系式递归算法实际上是使用了分而治之的方法，把大小为递归算法实际上是使用了分而治之的方法，把大小为n的原的原问题分成若干个大小为问题分成若干个大小为n/b的子问题，其中的子问题，其中a个子问题需要个子问题需要求解，而求解，而cnk是合并各个子问题的解需要的工作量，因此递是合并各个子问题的解需要的工作量，因此递归算法一般可以描述为：归算法一般可以描述为：+=1)(1)(ncnbnaTncnTk2.5 递归算法的分析递归算法的分析 =kkkbkkabanObannObanOnTb)()log()()(log定理定理2.1 设设T(n)是一个非递减函数，且满足通用分治递推式，是一个非递减函数，且满足通用分治递推式，则有：则有：证明：见课本证明：见课本22-23页页