算法分析与 及设计[绪论].pptVIP

算法设计与分析;学习目标;课程要求;教材和教参;内容安排;什么是算法（续）;例 求两个正整数m,n的最大公因子;例 求两个正整数最大公因子的一个实例;算法的五个重要特性;算法的五个重要特性;2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 例：整数的算术运算是“能行”的； 实数的算术运算是“不能行”的。;3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）;5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 准确理解算法和计算过程的区别： 不能终止的计算过程：操作系统 算法是“可以终止的计算过程” 算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。;算法的特性;算法和程序;算法学习的五个内容;算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性程序的证明 4）分析算法：算法时空特性分析 5）测试程序：“调试只能指出有错误，而不能指出它们不存在错误” 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础;2.如何分析算法;全面分析一个算法的两个阶段;例 频率计数例子;计算时间的渐进估计表示;时间的渐进估计表示;时间的渐进估计表示;算法的分类;n;典型的计算时间函数曲线;效率比速度更重要;举例：效率比速度更重要;举例：效率比速度更重要;时间的渐进估计表示;常用的整数求和公式;3. 如何表示算法;SPARKS语言的组成（1）;SPARKS语言的组成（2）;SPARKS语言的组成（3）;SPARKS语言的组成（4）;1.4 基本数据结构(略);1.4.3 集合的树表示和不相交集合的合并——树结构应用的实例;集合操作举例;方法一：位向量;方法二：集合元素表 ;方法三: 树 ;用树结构来表示集合;集合树表示法的具体实现;集合树表示法的具体实现（续）;数据结构;简单的合并与查找运算;查找元素F(9) ;U和F的性能问题——退化树 ;加权规则;加权规则(续);加权规则 ;使用加权规则的合并算法;Union F序列分析;引理1.3设T是一棵由算法UNION所产生的有n个结点的树。在T中没有结点的级数会大于[logn]+1。;例1.1;分析;压缩规则;使用压缩规则的查找算法;使用压缩规则的查找;1.5 递归和消去递归;递归例子：Fibonacci数列;用递归实现求最大公因数;GCD(22,8);消去递归;小结