算法设计技巧与分析算法基本概念之计算法.pptx

算法设计技巧与分析算法设计技巧与分析Algorithms Design Techniques and Analysis 南方医科大学医工学院南方医科大学医工学院 信息技术系信息技术系 第第1 1章章 算法分析基本概念算法分析基本概念Contento算法与程序算法与程序o简单的算法实例简单的算法实例o计算复杂性计算复杂性n时间复杂性时间复杂性n空间复杂性空间复杂性o分析计算方法分析计算方法Methodso估算算法运行时间的方法估算算法运行时间的方法：1）迭代计数：计算类循环的迭代次数；）迭代计数：计算类循环的迭代次数；2）操作计数：找出一个或多个）操作计数：找出一个或多个关键关键操作，确操作，确定这些关键操作所需要的执行时间；定这些关键操作所需要的执行时间；o实验方法实验方法：n利用编译器提供的时间函数来计算。利用编译器提供的时间函数来计算。Iterative Counto算法运行时间常常和算法运行时间常常和While循环及类似结构循环及类似结构的执行次数成正比。的执行次数成正比。o计算迭代次数将很好的表明算法的运行时间，计算迭代次数将很好的表明算法的运行时间，适用于搜索、排序、矩阵乘法等算法。适用于搜索、排序、矩阵乘法等算法。输入输入:n=,k 为正整数。为正整数。输出输出:第第4步的执行次数步的执行次数 count。1、count 02、while n 13、for j 1 to n4、count count+15、end for6、n n/27、end while 8、return countAnalysiso包含包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count；o对对 为正整数为正整数：while循环执行循环执行 K+1次，次，for循环执行循环执行n次，之后是次，之后是 n/2、n/4，1 次。次。o考察对象考察对象1 1：算法中第：算法中第4步的执行次数；步的执行次数；o第第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 Analysiso包含包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count；on n 取下列不同值时，内循环反复执行取下列不同值时，内循环反复执行：o考察对象考察对象1 1：算法中第：算法中第5步的执行次数；步的执行次数；o由于由于：o结论结论：第第5 5步执行步执行 次。次。o第第5 5步的执行次数是：步的执行次数是：输入输入:n=,k 为正整数。为正整数。输出输出:第第6步的执行次数步的执行次数 count。1、count 02、for i 1 to n3、j 24、while j n5、j 6、count count+17、end while 8、end for9、return countAnalysiso包含包含：两个嵌套循环和一个变量两个嵌套循环和一个变量 count；o输入输入：n 具有具有 形式，形式，k 为正整数。为正整数。o考察对象考察对象1 1：算法中第：算法中第6步的执行次数；步的执行次数；o对每个对每个forfor循环：循环：whilewhile的执行次数是的执行次数是 k+1=log log n+1o对于对于i i所取的每一个值所取的每一个值：当：当 时，执行时，执行while循环。循环。o结论结论：第第6 6步执行次数为步执行次数为输入输入:n=,k 为某个整数。为某个整数。输出输出:对于和对于和 n 之间的每个完全平方数之间的每个完全平方数 j,输出输出 。2、for j 1 to 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 Analysiso考察对象考察对象1 1：算法的运行时间；：算法的运行时间；o结论结论：算法的运行时间是：算法的运行时间是 。o假定假定：可以在可以在O(1)时间计算出来；时间计算出来；o内部内部forfor循环的执行次数：循环的执行次数：Meta Operationo定义定义1.11.1：n对任何计算步骤，它的代价总是以一个时对任何计算步骤，它的代价总是以一个时间常量为上界，而不管输入数据或执行的间常量为上界，而不管输入数据或执行的算法，我们称该计算步骤为算法，我们称该计算步骤为“元运算元运算”。o举例举例：n算术运算算术运算n比较和逻辑运算比较和逻辑运算n赋值运算赋值运算Basic Operation o定义定义1.6 1.6 如果算法中的一个元运算具有最高如果算法中的一个元运算具有最高频度，所有其他元运算频度均在它的频度的频度，所有其他元运算频度均在它的频度的常数倍内，则称这个元运算为常数倍内，则称这个元运算为基本运算基本运算。oCandidate：n搜索和排序算法中，选元素比较运算搜索和排序算法中，选元素比较运算n矩阵乘法算法中，选数量乘法运算矩阵乘法算法中，选数量乘法运算n链表遍历算法中，选设置或更新指针运算链表遍历算法中，选设置或更新指针运算n图的遍历算法中，选访问节点和节点计数图的遍历算法中，选访问节点和节点计数Example 1.26o考察对象考察对象：算法算法BOTTOMUPSORTBOTTOMUPSORT的确界；的确界；o基本运算基本运算：从算法从算法MERGEMERGE继承，元素的比较次数；继承，元素的比较次数；o当当n n是是2 2的幂时的幂时：算法所需要的元素比较的总次数算法所需要的元素比较的总次数在（在（n long n)/2n long n)/2和和 n log n n log n n+1 n+1 之间；之间；o即即：元素比较的次数是元素比较的次数是(n log n)(n log n)和和 (n log n)(n log n),也就是也就是(n log n)(n log n)；o可以证明可以证明：在在 n n 不是不是 2 2 的幂时，上述结论仍的幂时，上述结论仍然成立；然成立；Conclusion 由于算法由于算法BOTTOMUPSORTBOTTOMUPSORT用到的元素比较运算，用到的元素比较运算，在相差一个常数因子的意义下具有最大频度，在相差一个常数因子的意义下具有最大频度，我们可以得出结论，算法的运行时间和比较次我们可以得出结论，算法的运行时间和比较次数成正比。由此可知，算法的运行时间是数成正比。由此可知，算法的运行时间是 (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调用次数调用次数：n-1次；o元素比较总次数最多为元素比较总次数最多为：o错误结论：错误结论：算法的运行时间是算法的运行时间是 。Why？o注意注意：当两个算法的输入相同的时候，算：当两个算法的输入相同的时候，算法法MODINSETIONSORTMODINSETIONSORT和算法和算法INSETIONSORTINSETIONSORT的元素赋值次数完全一样，这已被证明是的元素赋值次数完全一样，这已被证明是 。o结论结论：算法的运行时间是：算法的运行时间是 。Special Instanceo在有些算法里，所有的元运算都不是基本运算。在有些算法里，所有的元运算都不是基本运算。o例如：两种或者更多的运算结合在一起的频度例如：两种或者更多的运算结合在一起的频度与算法的运行时间成正比。与算法的运行时间成正比。o方法：用执行这些运算的总次数的函数来表示方法：用执行这些运算的总次数的函数来表示运行时间。运行时间。选择一种或多种（如加、乘和比较等）元运算，然后选择一种或多种（如加、乘和比较等）元运算，然后确定这种（些）操作分别执行了多少次。确定这种（些）操作分别执行了多少次。令令n代表程序的实例特征，那么代表程序的实例特征，那么 TP的计算公式为：的计算公式为：TP（n）=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+c1、c2、c3、c4分别表示，一次分别表示，一次加、减、乘、加、减、乘、除运算所需的时除运算所需的时间。函数间。函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示分别表示程序程序P中，所使用的加、减、乘、中，所使用的加、减、乘、除运算的次数。除运算的次数。这种方法是否成功取这种方法是否成功取决于识别元运算的能决于识别元运算的能力，这些元运算对时力，这些元运算对时间复杂性的影响最大。间复杂性的影响最大。Meta Operation Count二分搜索选择排序插入排序合并排序Example 1.28已知已知：有一个有一个 n n 个整数的数组个整数的数组A A11 nn和一个正整数和一个正整数 k k ，11k kn n，要求要求：把把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)。注意，在这个。注意，在这个例子中，能够通过对循环次数计数来获得运行时例子中，能够通过对循环次数计数来获得运行时间的精确测度，这是因为在每一个循环中算法用间的精确测度，这是因为在每一个循环中算法用的时间量不变，循环的总数是的时间量不变，循环的总数是 k+(n-k)=nk+(n-k)=n。AnalysisBest and Worsto最坏情况分析最坏情况分析：n在所有大小为在所有大小为n的输入中选择代价最大的进行分的输入中选择代价最大的进行分析。析。o平均情况分析平均情况分析：n考虑所有大小为考虑所有大小为n的输入的平均时间。的输入的平均时间。Exampleo分析算法分析算法INSERTIONSORT，令A1n=1,2,n，A中元素共有中元素共有n!种排种排列，则对于不同的排列，算法的运行时间是列，则对于不同的排列，算法的运行时间是不同的。不同的。o考虑考虑：na:数组数组A中的元素已按降序排列；中的元素已按降序排列；nb:数组数组A中的元素为随机顺序；中的元素为随机顺序；nc:数组数组A中的元素已按升序排列；中的元素已按升序排列；Figure 1.6输入大小运行时间最好情况平均情况最坏情况n2/2n2/4nWorsto在最坏情况假设下，许多算法的上下界合一。在最坏情况假设下，许多算法的上下界合一。o考虑算法考虑算法INSERTIONSORT，由于其运行由于其运行时间是时间是O(n2)，且在最坏情况下算法的运行时，且在最坏情况下算法的运行时间是间是(n2)，则可以使用更强的符号，则可以使用更强的符号，即该，即该算法在最坏情况下是算法在最坏情况下是(n(n2)的的。注意：并不是所有的算法在最坏情况下的上下注意：并不是所有的算法在最坏情况下的上下界总会重合！界总会重合！Example 1.29o输入输入：一个元素：一个元素x x和一个有和一个有n n个元素的排序数组个元素的排序数组A A。o过程过程：1.if 1.if n为奇数 then then k BINARYSEARCH(A，x)2.else k LINEARSEARCH(A，x)o当当n n是偶数时是偶数时：算法算法LINEARSEARCH的运行的运行时间是时间是O(n)的，因此其运行时间是的，因此其运行时间是O(n)。考虑：最坏情况下考虑：最坏情况下，算法算法LINEARSEARCH的运行时间是不是的运行时间是不是(n)(n)的？的？Analysiso证明证明：不存在一个阈值不存在一个阈值 ,使对所有的使对所有的 ，都存在某一大小为，都存在某一大小为n n的输入，使算法对于某的输入，使算法对于某一常数一常数c c至少用至少用 cn cn 的时间。的时间。o因此因此：最坏情况下运行时间不是：最坏情况下运行时间不是(n)(n)的。的。o注意注意：n对于对于n的无限多个值运行时间是的无限多个值运行时间是(n)的，并的，并不意味着在最坏情况下运行时间是不意味着在最坏情况下运行时间是(n)的。的。Averageo平均情况运行时间：在所有大小为平均情况运行时间：在所有大小为n的输入的输入的平均时间。的平均时间。o需要预先知道输入的分布，即所有输入出现需要预先知道输入的分布，即所有输入出现的概率。的概率。o平均情况分析是复杂和冗长的。平均情况分析是复杂和冗长的。Example 1.30o考察对象考察对象：算法算法LINEARSEARCH的平均情况。的平均情况。o假定假定1 1：A包含包含1到到n，这意味着所有，这意味着所有A中的元中的元素都是不同的。素都是不同的。o假定假定2 2：A中每一个元素中每一个元素y以相等可能性出现在数以相等可能性出现在数组的任意位置上，即对于所有的组的任意位置上，即对于所有的 的概率是的概率是1/n。o则则：为找到为找到 x 位置，执行的比较次数的平均值是位置，执行的比较次数的平均值是:这表明在平均情况下，为找到这表明在平均情况下，为找到 x 位置，算位置，算法要执行（法要执行（n+1)/2 次元素比较，因此算法次元素比较，因此算法LINEARSEARCH的时间复杂性在平均情况的时间复杂性在平均情况下是下是 的。的。AnalysisExample 1.31o考察对象考察对象：算法算法INSERTIONSORT的平均情况。的平均情况。o假定假定1 1：A包含包含1到到n的数字，这意味着的数字，这意味着A中所中所有的元素都是不同的。有的元素都是不同的。o假定假定2 2：数字数字1，2，3，n的所有的所有n!个排列个排列 以相等可能性出现。以相等可能性出现。o则则：要将元素要将元素Ai插入插入A1i中合适的位置上，中合适的位置上，若这个位置是若这个位置是j，1ji，所执行的比较次数为：，所执行的比较次数为：Analysisoj=1j=1时时：i-j；o2ji2ji时时：i-j+1；由于这个合适位置在由于这个合适位置在A1 i中的概率是中的概率是1/i，则，则将将Ai插入到插入到A1 i中合适位置上所需要的平均中合适位置上所需要的平均比较次数是：比较次数是：则则：算法：算法INSERTIONSORT执行的平均比较次数是执行的平均比较次数是由于由于：因此因此：执行算法执行算法INSERTIONSORT的平均比较次数的平均比较次数Input Size and Instanceo一个算法执行性能的测度通常是它输入的大一个算法执行性能的测度通常是它输入的大小、顺序和分布等的函数。小、顺序和分布等的函数。o输入的大小作为一个数量，不是输入的精确输入的大小作为一个数量，不是输入的精确测度，它解释为从属于已设计或将要设计的测度，它解释为从属于已设计或将要设计的算法的问题。算法的问题。Size Measurement问题问题输入大小测度输入大小测度排序排序/搜索搜索数组或表中元素的数目数组或表中元素的数目图的算法图的算法图中边图中边/顶点的数目顶点的数目计算几何计算几何点点/顶点顶点/边边/线段线段/多边形的个数多边形的个数矩阵运算矩阵运算输入矩阵的维数输入矩阵的维数数论算法数论算法/密码学密码学输入的比特数输入的比特数/字数字数输入输入:一个正整数一个正整数 n 和一个数组和一个数组 A i,A j =j,1 j n。输出输出:1、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。输出输出:。Analysiso数论：是研究数的性质的一门学科。数论：是研究数的性质的一门学科。数学是科学的皇后，数论是数学中的皇冠。数学是科学的皇后，数论是数学中的皇冠。高斯高斯算法算法输入输入输出输出时间复杂度时间复杂度FIRSTn、A1nSECONDk=