算法设计与分析电子教案P1.ppt

《算法设计与分析电子教案P1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LectureNotesSeriesonComputingVol.7AlgorithmsDesignTechniquesandAnalysisM.H.Alsuwaiyel著1主要内容介绍第1部分算法引论算法分析基本概念数学预备知识数据结构基本知识堆和不相交集数据结构第2部分递归技术递归法分治法动态规划第3部分最优割技术贪心算法图的遍历法2主要内容介绍（续）第4部分问题复杂性NP完全问题计算复杂性引论下界问题第6部分克服困难性回溯法随机算法近似算法第6部分域指定问题的迭代改进网络流问题匹配问题第7部分计算几何技术几何扫描问题Voronoi图解问题3第1

2、部分算法引论主要知识点：1.算法分析基本概念重点对给定算法的时间和空间分析2.算法分析数学预备知识重点算法分析数学背景知识:求和、递推3.数据结构基本知识重点算法设计的基本数据结构4.堆与不相交集数据结构重点优先队列和不相交集数据结构4第1节算法分析基本概念1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4二分搜索分析1.5归并两个有序表1.6排序算法1.7BottomUoSort1.8算法复杂性分析1.9最优算法2.0平摊分析2.1输入大小和实例本章主要知识点：51.1算法与程序输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一

3、个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法：程序：61.从机器语言到高级语言的抽象1.2表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）

4、高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；72.抽象数据类型1.2表达算法的抽象机制抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维

5、护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。8在本书中，采用伪程序设计语言描述算法。采用类似自然语言和程序设计语言结合的方式来描述算法。1.3描述算法91.4二分搜索假定对有序线性集合进行查找元素x是否在集合中。目的设计比较次数少的最优算法（对于搜索的主要开销在元素比较上）。以下的算法均在升序的有序数组A[1:n]数据结构基础上操作。搜索A[j]=x，如不存在则j=0，否则j为所求元素位置算法1.1顺序比较效率分析算法1.2二分搜索效率分析10对

6、于算法1.1效率差，最坏比较次数为数组元素个数，最好为1；对于算法1.2效率差，最坏比较次数为logn+1，最好为1；结论算法1.2最优定理1.1对于大小为n的排序数组，二分搜索算法执行比较的最大次数为logn+1.111.5归并两个有序表将两个有序的表合并成一个大的有序表。目的分析比较次数。算法1.3分析1：元素比较次数与被归并的两个有序表的大小有关。如果n=n1+n2，n1<=n2，则比较次数界于n1与n-1之间；特别n1=n2，则比较次数界于n/2与n-1之间分析2：有辅助数组存在，元素赋值次数为2n121.6排序算法算法1.4选择排序算法1.

7、4分析元素比较次数为n(n-1)/2，元素赋值次数界于0~3(n-1)之间。算法1.5插入排序算法1.5分析元素比较次数界于n-1~n(n-1)/2之间元素赋值次数为元素比较次数加n-1131.7BottomUpSort前面的排序算法对n元素排序元素比较次数与n2成正比。效率不高。思想：对n个元素的数组，首先合并n/2个连续元素对，生成大小为2的n/2个有序对；如剩余1个元素则假如下一轮迭代；再合并n/4个连续的2个元素对序列，生成n/4个大小为4的有序序列，如剩余1或2个元素则将其进入下一轮迭代；如剩余3个元素则将2个元素和1个元素合并成3个元素的

8、有序对；继续上诉过程，在第j次迭代中，合并n/2j对大小为2j的有序序列，生成大小为2j的n/2j个有序序列