算法设计技巧与分析 基于递归的技术 华南师范大学计算机学院

发布于:2021-10-27 10:41:21

Design Techniques and Analysis

Algorithms:

算法设计技巧与分析
陈卫东 chenwd@scnu.edu.cn 华南师范大学计算机学院
2008-12-8

基于递归的技术
n

递归 — — 是将问题分解为一个或者多个与原问题结构相同的
子问题,并由这些子问题的解得到原问题解的过程。

n
n

三种情形
n

n

归纳法,或尾递归 -----第五章 归纳法 子问题无重叠的情形 -----第六章 分治法 子问题有重叠的情形(用空间换时间) -----第七章 动态规划
陈卫东(W.D.Chen) 华南师范大学 计算机学院 1

第五章 归纳
n n n n n n

引言 基数排序(Radix Sort) 求整数次幂 多项式求值 产生排列 找主元素(Majority Element)

陈卫东(W.D.Chen)

华南师范大学 计算机学院

2

引言
n

n

n n n

数学归纳法的基本模式 (用于证明问题) 递归算法的基本模式 (用于求解问题) 递归算法的特点 例 1 选择排序(Selection Sort ) 例 2 插入排序( Insertion Sort)

陈卫东(W.D.Chen)

华南师范大学 计算机学院

3

数学归纳法的基本模式 (用于证明问题)
1. n=1, f(1)… … 成立; 2. 假设k<n结论成立,即f(k)… … 成立。 利用f(1)、… 、f(n-1)得证f(n)… 也成立。 3. 综上所述, 对于所有的n≥1,都有f(n)… … 成立。 归纳原理

陈卫东(W.D.Chen)

华南师范大学 计算机学院

4

递归算法的基本模式 (用于求解问题)
1. n=1, f(1) … (直接求解); 2. (递归)求解f(k)… (k<n), 并利用f(1)、… 、f(n-1)得f(n) … 注:一般来说,求f(k)(k<n)比求f(n)要容易, 关键在于要有办法由f(1)、… 、f(n-1)得到f(n) 。 归纳原理

陈卫东(W.D.Chen)

华南师范大学 计算机学院

5

递归算法的基本模式 (用于求解问题)
递归算法的框架: f(n) { n=1, f(1) … (直接求解); n>1, (递归)求解f(k)… (k<n) 并利用f(1)、… 、f(n-1)求得f(n)… ; } 注:关键步骤是由f(1)、… 、f(n-1)得到f(n)。 其正确性可使用归纳法来证明。

陈卫东(W.D.Chen)

华南师范大学 计算机学院

6

递归算法的特点
优点: 1. 读写简明; 2. 算法的正确性易于用数学归纳法来证; 3. 算法的复杂性往往可利用递归关系来分析 缺点: 1. 算法的执行流程不易理解; 2. 递归调用往往需要额外的时空开销

陈卫东(W.D.Chen)

华南师范大学 计算机学院

7

例1
n

选择排序(Selection sort )

算法思想 A[i… n]排序 { 若n>i, 将A[i… n]中最小元素找出,并换至A[i]处; A[i+1… n]排序; } 图示 复杂度
陈卫东(W.D.Chen) 华南师范大学 计算机学院 8

n n

例2 插入排序(Insertion sort )
n

算法思想 A[1… i]排序 { 若 i>1, A[1… i-1]排序 ; 将 A[i]插入到A[1… i-1]中的适当位置处; } 图示 复杂度

n n

陈卫东(W.D.Chen)

华南师范大学 计算机学院

9

基数排序(Radix Sort)
n

问题 要求对 n个数的序列L={a1, a2 , … , an}进行排序,其中每 个数恰好由 k位数字组成,每位数字均取自{0,1,… ,9}。 算法思想 : 对于k使用归纳法。 实例 Algorithm 5.3 RADIXSORT 复杂度 n 时间复杂度: Θ(kn) n 空间复杂度: Θ(n)
陈卫东(W.D.Chen) 华南师范大学 计算机学院 10

n n n n

求整数次幂
n n

n n n

问题 求实数x的n次幂,即xn ,其中n为一个非负整数。 算法思想 计算xn { 计算xm ; // m=?n/2? 若n是偶数,则xn =(xm)2, 若n是奇数,则xn =x(xm)2 } Algorithm 5.4 EXPREC Algorithm 5.5 EXP 时间复杂度: Θ(log n)
陈卫东(W.D.Chen) 华南师范大学 计算机学院 11

多项式求值
n

问题 求下列实系数多项式的值: Pn(x)=anxn+ an-1xn-1 + … + a1x + a0 算法思想(Horner’ s rule) Pn(x)= xPn-1(x) + a0 Algorithm 5.6 HORNER 时间复杂度: Θ(n)
陈卫东(W.D.Chen) 华南师范大学 计算机学院 12

n

n

n

产生排列(Generating Permutations)
n

n

问题 要求产生 1,2,… ,n的所有排列。 算法1 n 思想 1[2,3,… ,n的排列], 2[1,3,… ,n的排列],… … , n[1,2,… ,n-1的排列]。 n Algorithm 5.7 PERMUTATIONS1 n 时间复杂度: Θ(nn!)
陈卫东(W.D.Chen) 华南师范大学 计算机学院 13

产生排列(Generating Permutations)
n

算法2 n 思想 n [× × … × × ] [× ] n [× … × × ],… … , [ × × … × × ]n。 n Algorithm 5.8 PERMUTATIONS2 n 时间复杂度: Θ(nn!)

陈卫东(W.D.Chen)

华南师范大学 计算机学院

14

找主元素(Finding the Majority 
Element)
n

问题 序列A[1..n]中是存在主元素?若有请找出来。A中主 元素是指在A中出现次数多于?n/2?次的元素。 算法1— — 穷举法 时间复杂度: Θ(n2) 算法2— — 排序 时间复杂度: Θ(n log n) 算法3— — 找中值 时间复杂度: Θ(n)
陈卫东(W.D.Chen) 华南师范大学 计算机学院 15

n

n

n

找主元素(Finding the Majority 
Element)
n

算法4 n 算法思想 命题 5.1 如果删去原序列中的两个不同元素,则原序列 中的主元素仍然在剩下的序列中.
n n

Algorithm 5.9 MAJORITY 时间复杂度— — Θ(n)

陈卫东(W.D.Chen)

华南师范大学 计算机学院

16

小结
n

归纳与递归算法之间的关系 应用 n 产生排列 n 产生组合

n

陈卫东(W.D.Chen)

华南师范大学 计算机学院

17

作业
n
n n

Page 99-101
5.8 5.9

思考题:5.23, 5.24, 5.31, 5.32, 5.33

陈卫东(W.D.Chen)

华南师范大学 计算机学院

18


相关推荐

最新更新

猜你喜欢