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

1.5 递归和消去递归 递归 直接调用自己或间接通过一些语句调用自己 优点：描述某些数学问题非常自然，证明算法很容易。 缺点：执行时间、空间消耗多 一个递归问题可分为“回推”和“递推”两个阶段 未知 已知 递推 回推 递归例子：Fibonacci数列 定义 F(n)= 1, n=0 1, n=1 F(n-1)+F(n-2), n1 非递归部分,终止条件 递归部分,起始条件 求Fibonacci数列算法 Procedure F(n) integer n if n≤1 then return(1) else return(F(n-1)+F(n-2)) end if End F 用递归实现求最大公因数 Procedure GCD(a,b) if b=0 then return(a) else return(GCD(b,a mod b)) endif End GCD 例如：a=22 , b=8 求GCD(22,8)=？ GCD(22,8) GCD(8,6) GCD(6,2) GCD(2,0) 2 回推 回推 回推 回推 递归 递归 递归 递归 用递归实现求最大公因数 结果为GCD(22,8)=2 消去递归 递归的优点：与数学定义相似，容易编写算法 递归的缺点：计算时间长，很多值都被重复计算了多次 消去递归 目的是克服递归时间空间的开销 解决方法：先使用递归，然后证明所设计的递归算法正确并且确信是一个好算法，再把递归消去，翻译成与之等价的只使用迭代的算法。 直接递归翻译成迭代过程的规则 小结 算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。 算法的五个重要特性 确定性、可行性、输入、输出、有穷性 算法分析是对一个算法需要多少时间很存储空间作定量分析。 用SPARKS语言写算法 基本数据结构 递归和消去递归 Fundamentals of Computer Algorithms 西南科技大学计算机学院软件教研室 * Fundamentals of Computer Algorithms 西南科技大学计算机学院软件教研室 * 举例：效率比速度更重要 To sort one million numbers, computer A takes: Computer B takes: Computer B runs 20 times faster than computer A! 时间的渐进估计表示 定义1.2 如果存在两个正常数c和n0，对于所有的n≥n0，有 |f(n)|≥ c|g(n)| 则记作：f(n)=Ω(g(n)) 定义1.3 如果存在两个正常数c1 ， c2和n0，对于所有的n≥n0，有 c1 |g(n)|≤ |f(n)|≤ c2 |g(n)| 则记作：f(n)=Θ(g(n)) 常用的整数求和公式 3. 如何表示算法 将算法的基本思想和基本步骤用语言表示出来，便于阅读并能很容易地用人工或机器翻译成其他实际使用的程序设计语言。 用SPARKS语言写算法 SPARKS语言的组成 基本数据类型 整型(integer),实型(float),布尔型(boolean),字符型(char) 保留字 具有特殊含义的标识符，用黑体字表示 SPARKS语言的组成（1） 变量命名规则 以字母开头，不允许使用特殊字符，不要太长，不允许与任何保留字重复。 语句：以分号作为语句结束的标志 赋值语句：变量 ? 表达式 布尔值：True False 逻辑运算符：and ，or ，not 关系运算符： ，≤ ，= ，≠ ， ，≥ 数组：任意整数下界和上界的多维数组 SPARKS语言的组成（2） 条件语句 if 条件 then s1 或 if 条件 then else s2 s1 endif endif Case语句 case : 条件 1:s1 … : 条件 n:sn :else :sn+1 endcase SPARKS语言的组成（3） 循环语句 while 条件 do loop S S Repeat until 条件 repeat For vble?start to finish by increment do S Repeat SPARKS语言的组成（4） 过程(函数) Procedure Name(参数列表) 说明部分 S Return(表达式) End Name 局部变量(local variabl) 在当前的过程中说明的变量 全局变量(global variabl) 在已包含当前过程的过程中说明为局部变量的变量 形式参数(formal para