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

《算法设计技巧与分析第1章算法基本概念之计算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计技巧与分析AlgorithmsDesignTechniquesandAnalysis南方医科大学医工学院信息技术系第1章算法分析基本概念Content算法与程序简单的算法实例计算复杂性时间复杂性空间复杂性分析计算方法Methods估算算法运行时间的方法：1）迭代计数：计算类循环的迭代次数；2）操作计数：找出一个或多个关键操作，确定这些关键操作所需要的执行时间；实验方法：利用编译器提供的时间函数来计算。IterativeCount算法运行时间常常和While循环及类似结构的执行次数成正比。

2、计算迭代次数将很好的表明算法的运行时间，适用于搜索、排序、矩阵乘法等算法。算法1.8COUNT1输入:n=,k为正整数。输出:第4步的执行次数count。1、count←02、whilen≥13、forj←1ton4、count←count+15、endfor6、n←n/27、endwhile8、returncountAnalysis包含：两个嵌套循环和一个变量count；对为正整数：while循环执行K+1次，for循环执行n次，之后是n/2、n/4，‥·，1次。考察对象1：算法中第4步的执行

3、次数；第4步的执行次数是：算法1.9COUNT2输入:正整数n。输出:第5步的执行次数count。1、n←02、fori←1ton4、forj←1tom5、count←count+16、endfor7、endfor8、returncount3、m←Analysis包含：两个嵌套循环和一个变量count；n取下列不同值时，内循环反复执行：考察对象1：算法中第5步的执行次数；由于：结论：第5步执行次。第5步的执行次数是：算法1.10COUNT3输入:n=,k为正整数。输出:第6步的执行次数count

4、。1、count←02、fori←1ton3、j←24、whilej≤n5、j←6、count←count+17、endwhile8、endfor9、returncountAnalysis包含：两个嵌套循环和一个变量count；输入：n具有形式，k为正整数。考察对象1：算法中第6步的执行次数；对每个for循环：while的执行次数是k+1=loglogn+1对于i所取的每一个值：当时，执行while循环。结论：第6步执行次数为算法1.11PSUM输入:n=,k为某个整数。输出:对于１和n之间的每

5、个完全平方数j,输出。2、forj←1tok3、sum[j]←04、fori←1toj26、endfor5、sum[j]←sum[j]+i7、endfor8、returnsum[1…k]1、k←Analysis考察对象1：算法的运行时间；结论：算法的运行时间是。假定：可以在O(1)时间计算出来；内部for循环的执行次数：MetaOperation定义1.1：对任何计算步骤，它的代价总是以一个时间常量为上界，而不管输入数据或执行的算法，我们称该计算步骤为“元运算”。举例：算术运算比较和逻辑运算赋值

6、运算BasicOperation定义1.6如果算法中的一个元运算具有最高频度，所有其他元运算频度均在它的频度的常数倍内，则称这个元运算为基本运算。Candidate：搜索和排序算法中，选元素比较运算矩阵乘法算法中，选数量乘法运算链表遍历算法中，选设置或更新指针运算图的遍历算法中，选访问节点和节点计数Example1.26考察对象：算法BOTTOMUPSORT的确界；基本运算：从算法MERGE继承，元素的比较次数；当n是2的幂时：算法所需要的元素比较的总次数在（nlongn)/2和nlogn–n+

7、1之间；即：元素比较的次数是Ω(nlogn)和Ο(nlogn),也就是Θ(nlogn)；可以证明：在n不是2的幂时，上述结论仍然成立；Conclusion由于算法BOTTOMUPSORT用到的元素比较运算，在相差一个常数因子的意义下具有最大频度，我们可以得出结论，算法的运行时间和比较次数成正比。由此可知，算法的运行时间是Θ(nlogn)。算法1.12MODINSERTIONSORT输入:n个元素的数组A[i]。输出:按非降序排列的数组A[1…i–1]。1、fori←2ton2、x←A[i]3、k

8、←MODBINARYSEARCH(A[1…i–1])4、forj←i–1downtok5、A[j+1]←A[j]6、endfor7、A[k]←x8、endforAnalysis考察对象1：算法的运行时间；算法MODBINARYSEARCH调用次数：n-1次；元素比较总次数最多为：错误结论：算法的运行时间是。Why？注意：当两个算法的输入相同的时候，算法MODINSETIONSORT和算法INSETIONSORT的元素赋值次数完全一样，这已被证明是。结论：算法的运行时间是。SpecialInsta