算法设计技巧与分析第1章算法基本概念之计算法ppt课件

《算法设计技巧与分析第1章算法基本概念之计算法ppt课件》由会员分享，可在线阅读，更多相关《算法设计技巧与分析第1章算法基本概念之计算法ppt课件（41页珍藏版）》请在装配图网上搜索。

1、算法设计技巧与分析算法设计技巧与分析Algorithms Design Techniques and Analysis 南方医科大学医工学院南方医科大学医工学院 信息技术系信息技术系 第第1 1章章 算法分析根本概念算法分析根本概念Contento算法与程序算法与程序o简单的算法实例简单的算法实例o计算复杂性计算复杂性o时间复杂性时间复杂性o空间复杂性空间复杂性o分析计算方法分析计算方法Methodso估算算法运转时间的方法：估算算法运转时间的方法：o 1 1迭代计数：计算类循环的迭代次数；迭代计数：计算类循环的迭代次数；o 2 2操作计数：找出一个或多个关键操操作计数：找出一个或多个关键操作

2、，确定这些关键操作所需求的执行时间；作，确定这些关键操作所需求的执行时间；o实验方法：实验方法：o利用编译器提供的时间函数来计算。利用编译器提供的时间函数来计算。Iterative Counto算法运转时间经常和算法运转时间经常和While循环及类似构造循环及类似构造的执行次数成正比。的执行次数成正比。o计算迭代次数将很好的阐明算法的运转时间，计算迭代次数将很好的阐明算法的运转时间，适用于搜索、排序、矩阵乘法等算法。适用于搜索、排序、矩阵乘法等算法。输入输入:n=,k 为正整数。为正整数。输出输出:第第4步的执行次数步的执行次数 count。k1、count 02、while n 13、for

3、 j 1 to n4、count count+15、end for6、n n/27、end while 8、return countAnalysiso包含：包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count count；o对对 为正整数：为正整数：whilewhile循环执行循环执行 o K+1 K+1次，次，forfor循环执行循环执行n n次，之后是次，之后是o n/2 n/2、n/4n/4，1 1 次。次。2,knk0011(2)21()222kkjjkjjnnnnn o调查对象调查对象1 1：算法中第：算法中第4 4步的执行次数；步的执行次数；o第第4 4步的执行次数是：步

4、的执行次数是：输入输入:正整数正整数 n。输出输出:第第5步的执行次数步的执行次数 count。1、n 02、for i 1 to n4、for j 1 to m 5、count count+16、end for7、end for8、return count3、m inAnalysiso包含：包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count count；on n 取以下不同值时，内循环反复执行：取以下不同值时，内循环反复执行：o ,/2,/3,/nnnn n o调查对象调查对象1 1：算法中第：算法中第5 5步的执行次数；步的执行次数；111(1)nnniiinnniiio由于：

5、由于：o结论：第结论：第5 5步执行步执行 次。次。(log)nno第第5 5步的执行次数是：步的执行次数是：niin1输入输入:n=,k 为正整数。为正整数。输出输出:第第6步的执行次数步的执行次数 count。k221、count 02、for i 1 to n3、j 24、while j n5、j 2j6、count count+17、end while 8、end for9、return countAnalysiso包含：包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count count；o输入：输入：n n 具有具有 方式，方式，k k 为正整数。为正整数。22ko调查对象调

6、查对象1 1：算法中第：算法中第6 6步的执行次数；步的执行次数；o对每个对每个forfor循环：循环：whilewhile的执行次数是的执行次数是o k+1=log log n+1 k+1=log log n+12422,2,2,2kjo对于对于i i所取的每一个值：当所取的每一个值：当o 时，执行时，执行whilewhile循环。循环。o结论：第结论：第6 6步执行次数为步执行次数为(loglog1)(loglog)nnnn 输入输入:n=,k 为某个整数。为某个整数。输出输出:对于和对于和 n 之间的每个完全平方数之间的每个完全平方数 j,输出输出 。2kjii12、for j 1 to

7、 k3、sum j 04、for i 1 to j2 6、end for5、sum j sum j +i7、end for8、return sum 1 k 1、k nAnalysiso调查对象调查对象1 1：算法的运转时间；：算法的运转时间；o结论：算法的运转时间是结论：算法的运转时间是 。1.5()no假定：假定：可以在可以在O(1)O(1)时间计算出来；时间计算出来；no内部内部forfor循环的执行次数：循环的执行次数：2231.5111(1)(21)1()()6jkkjijk kkjkn Meta Operationo定义定义1.11.1：o对任何计算步骤，它的代价总是以一个时间常对任

8、何计算步骤，它的代价总是以一个时间常量为上界，而不论输入数据或执行的算法，我量为上界，而不论输入数据或执行的算法，我们称该计算步骤为们称该计算步骤为“元运算。元运算。o举例：举例：o算术运算算术运算o比较和逻辑运算比较和逻辑运算o赋值运算赋值运算Basic Operation o定义定义1.6 1.6 假设算法中的一个元运算具有最高频假设算法中的一个元运算具有最高频度，一切其他元运算频度均在它的频度的常数度，一切其他元运算频度均在它的频度的常数倍内，那么称这个元运算为根本运算。倍内，那么称这个元运算为根本运算。oCandidate：o搜索和排序算法中，选元素比较运算搜索和排序算法中，选元素比较

9、运算o矩阵乘法算法中，选数量乘法运算矩阵乘法算法中，选数量乘法运算o链表遍历算法中，选设置或更新指针运算链表遍历算法中，选设置或更新指针运算o图的遍历算法中，选访问节点和节点计数图的遍历算法中，选访问节点和节点计数Example 1.26o调查对象：算法调查对象：算法BOTTOMUPSORTBOTTOMUPSORT确实界；确实界；o根本运算：从算法根本运算：从算法MERGEMERGE承继，元素的比较次数；承继，元素的比较次数；o当当n n是是2 2的幂时：算法所需求的元素比较的总次的幂时：算法所需求的元素比较的总次数在数在n long n)/2n long n)/2和和 n log n n+1

10、 n log n n+1 之间；之间；o即：元素比较的次数是即：元素比较的次数是(n log n)(n log n)和和(n (n log n),log n),也就是也就是(n log n)(n log n)；o可以证明：在可以证明：在 n n 不是不是 2 2 的幂时，上述结论的幂时，上述结论依然成立；依然成立；Conclusion 由于算法由于算法BOTTOMUPSORTBOTTOMUPSORT用到的元素比较运算，用到的元素比较运算，在相差一个常数因子的意义下具有最大频度，在相差一个常数因子的意义下具有最大频度，我们可以得出结论，算法的运转时间和比较次我们可以得出结论，算法的运转时间和比较

11、次数成正比。由此可知，算法的运转时间是数成正比。由此可知，算法的运转时间是 (n log n)(n log n)。输入输入:n 个元素的数组个元素的数组 A i。输出输出:按非降序陈列的数组按非降序陈列的数组A 1 i1 。1、for i 2 to n2、x A i 3、k MODBINARYSEARCH(A 1 i1 )4、for j i 1 downto k5、A j+1 A j 6、end for7、A k x8、end forAnalysiso调查对象调查对象1 1：算法的运转时间；：算法的运转时间；o算法算法MODBINARYSEARCHMODBINARYSEARCH调用次数：调用次

12、数：n-1n-1次；次；o元素比较总次数最多为：元素比较总次数最多为：11211(log(1)1)1log1log(log)nnniiiinininn o错误结论：算法的运转时间错误结论：算法的运转时间是是 。(log)nnWhy？)(2nOo留意：当两个算法的输入一样的时候，算留意：当两个算法的输入一样的时候，算法法MODINSETIONSORTMODINSETIONSORT和算法和算法INSETIONSORTINSETIONSORT的元素赋值次数完全一样，这已被证明的元素赋值次数完全一样，这已被证明是是 。o结论：算法的运转时间是结论：算法的运转时间是 。)(2nOSpecial Inst

13、anceo在有些算法里，一切的元运算都不是根本运算。在有些算法里，一切的元运算都不是根本运算。o例如：两种或者更多的运算结合在一同的频度例如：两种或者更多的运算结合在一同的频度与算法的运转时间成正比。与算法的运转时间成正比。o方法：用执行这些运算的总次数的函数来表示方法：用执行这些运算的总次数的函数来表示运转时间。运转时间。选择一种或多种如加、乘和比较等元运算，然选择一种或多种如加、乘和比较等元运算，然后确定这种些操作分别执行了多少次。后确定这种些操作分别执行了多少次。令令n代表程序的实例特征，那么代表程序的实例特征，那么 TP的计算公式为：的计算公式为：TPn=c1ADD(n)+c2SUB(

14、n)+c3MUL(n)+c4DIV(n)+c1、c2、c3、c4分别表示，一分别表示，一次加、减、乘、次加、减、乘、除运算所需的除运算所需的时间。函数时间。函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表分别表示程序示程序P中，所运用的加、减、中，所运用的加、减、乘、除运算的次数。乘、除运算的次数。这种方法能否胜利取这种方法能否胜利取决于识别元运算的才决于识别元运算的才干，这些元运算对时干，这些元运算对时间复杂性的影响最大。间复杂性的影响最大。Meta Operation CountExample 1.28知：有一个知：有一个 n n 个整数的数组个整数的数组A1 nA1 n和

15、一个正整数和一个正整数 k k，1kn1kn，要求：把要求：把A A中前中前k k 个整数相乘，把余下的相加。个整数相乘，把余下的相加。1.prod 1;sum 02.for j 1 to k3.prod prod A j 4.end for5.for j k+1 to n6.sum sum+A j 7.end for这样可以得出结论，存在有这样可以得出结论，存在有 n n 个元运算：乘法个元运算：乘法和加法，这意味着界是和加法，这意味着界是(n)(n)。留意，在这个。留意，在这个例子中，可以经过对循环次数计数来获得运转时例子中，可以经过对循环次数计数来获得运转时间的准确测度，这是由于在每一个

16、循环中算法用间的准确测度，这是由于在每一个循环中算法用的时间量不变，循环的总数是的时间量不变，循环的总数是 k+(n-k)=n k+(n-k)=n。AnalysisBest and Worsto最坏情况分析：最坏情况分析：o在一切大小为在一切大小为n n的输入中选择代价最大的进的输入中选择代价最大的进展分析。展分析。o平均情况分析：平均情况分析：o思索一切大小为思索一切大小为n n的输入的平均时间。的输入的平均时间。Exampleo分析算法分析算法INSERTIONSORT，令，令A1n=1,2,n，A中元素共有中元素共有n!种陈列，那么对于不同的陈列，算法的运转种陈列，那么对于不同的陈列，算

17、法的运转时间是不同的。时间是不同的。o思索：思索：oa:a:数组数组A A中的元素已按降序陈列；中的元素已按降序陈列；ob:b:数组数组A A中的元素为随机顺序；中的元素为随机顺序；oc:c:数组数组A A中的元素已按升序陈列；中的元素已按升序陈列；Figure 1.6输入大小运转时间最好情况平均情况最坏情况n2/2n2/4nWorsto在最坏情况假设下，许多算法的上下界合一。在最坏情况假设下，许多算法的上下界合一。o思索算法思索算法INSERTIONSORT，由于其运，由于其运转时间是转时间是O(n2)，且在最坏情况下算法的，且在最坏情况下算法的运转时间是运转时间是(n2)，那么可以运用更强

18、的，那么可以运用更强的符号符号，即该算法在最坏情况下是，即该算法在最坏情况下是(n2)的。的。留意：并不是一切的算法在最坏情况下的上留意：并不是一切的算法在最坏情况下的上下界总会重合！下界总会重合！Example 1.29o输入：一个元素输入：一个元素x x和一个有和一个有n n个元素的排序数组个元素的排序数组A A。o过程：过程：o 1.if n 1.if n为奇数为奇数 then k BINARYSEARCH(A then k BINARYSEARCH(A，x)x)o 2.else k LINEARSEARCH(A 2.else k LINEARSEARCH(A，x)x)o当当n n是偶数

19、时：算法是偶数时：算法LINEARSEARCHLINEARSEARCH的运转时间是的运转时间是O(n)O(n)的，因此其运转时间是的，因此其运转时间是O(n)O(n)。思索：最坏情况下，算法思索：最坏情况下，算法LINEARSEARCH的运转时间是不是的运转时间是不是(n)的？的？Analysiso证明：不存在一个阈值证明：不存在一个阈值 ,使对一切使对一切的的 ，都存在某一大小为，都存在某一大小为n n的输入，使算的输入，使算法对于某一常数法对于某一常数c c至少用至少用 cn cn 的时间。的时间。0n0nno因此：最坏情况下运转时间不是因此：最坏情况下运转时间不是(n)(n)的。的。o留

20、意：留意：o对于对于n n的无限多个值运转时间是的无限多个值运转时间是(n)(n)的，并的，并不意味着在最坏情况下运转时间是不意味着在最坏情况下运转时间是(n)(n)的。的。Averageo平均情况运转时间：在一切大小为平均情况运转时间：在一切大小为n的输入的输入的平均时间。的平均时间。o需求预先知道输入的分布，即一切输入出现需求预先知道输入的分布，即一切输入出现的概率。的概率。o平均情况分析是复杂和冗长的。平均情况分析是复杂和冗长的。Example 1.30o调查对象：算法调查对象：算法LINEARSEARCHLINEARSEARCH的平均情况。的平均情况。o假定假定1 1：A A包含包含1

21、 1到到n n，这意味着一切，这意味着一切A A中中的元素都是不同的。的元素都是不同的。o假定假定2 2：A A中每一个元素中每一个元素y y以相等能够性出如今数以相等能够性出如今数组的恣意位置上，即对于一切的组的恣意位置上，即对于一切的 的概率是的概率是1/n1/n。,yA yA jo那么：为找到那么：为找到 x x 位置，执行的比较次数的平均位置，执行的比较次数的平均值是值是:这阐明在平均情况下，为找到这阐明在平均情况下，为找到 x 位置，算位置，算法要执行法要执行n+1)/2 次元素比较，因此算次元素比较，因此算法法LINEARSEARCH的时间复杂性在平均的时间复杂性在平均情况下是情况

22、下是 的。的。Analysis11111(1)1()22nnjjn nnT njjnnn()nExample 1.31o调查对象：算法调查对象：算法INSERTIONSORTINSERTIONSORT的平均情况。的平均情况。o假定假定1 1：A A包含包含1 1到到n n的数字，这意味着的数字，这意味着A A中一切的元素都是不同的。中一切的元素都是不同的。o假定假定2 2：数字：数字1 1，2 2，3 3，n n的一切的一切n!n!个陈列个陈列o 以相等能够性出现。以相等能够性出现。o那么：要将元素那么：要将元素AiAi插入插入A1iA1i中适宜的位中适宜的位置上，假设这个位置是置上，假设这个

23、位置是j j，1ji1ji，所执行的比，所执行的比较次数为：较次数为：Analysisoj=1j=1时：时：i-j i-j；o2ji2ji时：时：i-j+1 i-j+1；由于这个适宜位置在由于这个适宜位置在A1 i中的概率是中的概率是1/i，那么那么将将Ai插入到插入到A1 i中适宜位置上所需求的平中适宜位置上所需求的平均均比较次数是：比较次数是：12111111111222iijjiijfijiiiiiiii 那么：算法那么：算法INSERTIONSORTINSERTIONSORT执行的平均比较次数是执行的平均比较次数是222111(1)11131()2242244nnniiiin nnnn

24、iii 由于：由于：11ln(1)ln1ninni因此：执行算法因此：执行算法INSERTIONSORTINSERTIONSORT的平均比较次数的平均比较次数223ln()44nnnn Input Size and Instanceo一个算法执行性能的测度通常是它输入的大一个算法执行性能的测度通常是它输入的大小、顺序和分布等的函数。小、顺序和分布等的函数。o输入的大小作为一个数量，不是输入的准确输入的大小作为一个数量，不是输入的准确测度，它解释为从属于已设计或将要设计的测度，它解释为从属于已设计或将要设计的算法的问题。算法的问题。Size Measurement问题问题输入大小测度输入大小测度

25、排序排序/搜索搜索数组或表中元素的数目数组或表中元素的数目图的算法图的算法图中边图中边/顶点的数目顶点的数目计算几何计算几何点点/顶点顶点/边边/线段线段/多边形的个数多边形的个数矩阵运算矩阵运算输入矩阵的维数输入矩阵的维数数论算法数论算法/密码学密码学输入的比特数输入的比特数/字数字数输入输入:一个正整数一个正整数 n 和一个数组和一个数组 A i,A j =j,1 j n。输出输出:njjA11、sum 02、for j 1 to n3、sum sum+A j 4、end for5、return sum1、sum 02、for j 1 to n3、sum sum+j4、end for5、return sum输入输入:正整数正整数 n。输出输出:。nji1Analysiso数论：是研讨数的性质的一门学科。数论：是研讨数的性质的一门学科。数学是科学的皇后，数论是数学中的皇冠。数学是科学的皇后，数论是数学中的皇冠。高斯高斯算法算法输入输入输出输出时间复杂度时间复杂度FIRSTn、A1nSECONDk=()n(2)k1 njA j1njj)1log(n