计算机算法导论-算法选讲
- 格式:doc
- 大小:14.70 KB
- 文档页数:12
本文由mysky_2012贡献
南开大学信息技术科学学院
杨巨峰
Webster词典
? 算法即在有限步骤内解一个数学问题的过程,步骤中常常 包括某一操作的重复。更广义地说,一个算法就是为解一 个问题或实现某一目标的逐步过程
D.E.Knuth
? 算法是一个有穷规则的集合,其中之规则规定了一个解决 某一特定类型的问题的运算序列。此外,他还应具有如下 五个重要特性
有穷性 确定性 输入 输出 能行性 《计算机程序设计艺术》
2
1. 2. 3. 4.
算法评估与分析 MAXMIN问题 排序问题 字符串匹配
3
4
正确性
? 原则上应该证明算法对于任意合理的输入都正确 ? 实际中常用推理法证明
时间代价
? 必须抛弃的评价指标
算法运行的实际执行时间 运行过程中所执行的指令条数 运行过程中程序循环的次数
空间代价 最优性
5
是指算法运行中起主要作用且花费最多时间的操作
? 两个实数矩阵的乘法问题中,矩阵的实数元素之间的数乘 ? 对N个整数进行排序的算法中,整数间的比较和交换
引入基本操作的概念,用其执行次数来度量算法的 时间代价,是算法分析的基础
6
算法的运行时间代价除了与算法本身的基本操作数 有关外,还与问题实例的长度有关,即受输入规模 影响
? ? ? ? 排序问题:待排序元素序列的长度n 矩阵乘积:n阶方阵的阶数n 图问题:图的顶点数n和边数m 字符串匹配问题:文本T的长度n
T(n)
? 算法的时间复杂度,用问题实例长度的函数表示 ? 也就是用该算法用于问题长度为n的实例所需要的基本操 作次数来刻画
7
如果解决问题P的算法A和算法B,其时间复杂度分 别是TA(n)和TB(n),则判断A、B性能优劣的标准是 查看在n足够大时TA(n)和TB(n)的大小关系
8
对于同一算法,如果有相同的问题长度,但采用不同的输入,其时间 代价一般也不同。因此在实际的算法分析中,复杂度函数值T(n)不是 唯一的 设Dn为问题P的所有长度为n的实例集合,输入实例I∈Dn,t(I)是用 来解决问题P的算法A在以I为输入时的执行代价(基本操作数),则 算法A的最坏情形时间复杂度和最好情形时间复杂度定义如下
W (n) = MAX {t ( I )}
I ∈D n
B(n) = MIN{t ( I )}
I ∈D n
一般地,T (n) = W (n)
9
InsertSort
void InsertSort(int A[], int n) { for(int i=2;i<=n;i++) { int V = A[i]; int j=i-1;
while((A[j]>V)&;&;(j>0)) { A[j+1]=A[j]; j=j-1; 1 2 3 4 5 6 7 8 9 10 } 10 9 8 7 6 5
4 3 2 1 A[j+1]=V; 3 7 4 5 10 2 9 6 1 8 return; } }
9次比较 45次比较 ?次比较
10
许多实际问题的可能实例集是一个极大的集合,即使把问 题长度限定为n,实例集Dn依然很大。其中使算法A耗费 最大代价W(n)的实例往往只占很小的一部分,而大多数实 例耗费的代价常常远小于W(n),因此转而使用期望复杂度 或称平均情形复杂度评价算法性能
A(n) =
I ∈D n
∑ P( I )t ( I )
11
解析表达式 阶表达式
? O ? ? ? θ
多项式函数和指数函数
12
形式化定义
? 称复杂度函数T(n)是O(f(n)),即T(n)=O(f(n)),如果存在 常数c>0与n0,当n>n0时有T(n)<=cf(n),例如:
T1(n)=(n+1)/2=O(n) c=1,n0=1 T2(n)=3n2+4n+5=O(n2) c=10,n0=2 ? T1(n)=O(n2)和T2(n)=O(n3) 也是对的
13
形式化定义
? 称复杂度函数T(n)是?(f(n))的,即T(n)=?(f(n)),如果存 在常数c>0与n0,当n>n0时有T(n)>=cf(n),例如:
T1(n)=(n+1)/2=?(n) c=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c=3,n0=1
? T1(n)=O(1)和T2(n)=O(n) 也是对的
14
形式化定义
? 称复杂度函数T(n)是θ(f(n))的,即T(n)=θ(f(n)),如果存在 常数c1>0,c2>0与n0,当n>n0时有 c1f(n)>=T(n)>=c2f(n),例如:
T1(n)=(n+1)/2=?(n) c1=1,c2=0.5,n0=1 T2(n)=3n2+4n+5=?(n2) c1=10,c2=3,n0=2
? 显然如果T(n)=O(f(n))而且T(n)=?(f(n)),则容易得到 T(n)=θ(f(n))
15
类型 1 logn n nlogn n2 n3 2n n!
名称 常量 对数 线性 n-log-n 平方 立方 指数 阶乘
说明 效率最高,但是很少有算法达到 算法的每一次循环都会消除问题规模的一个常数因子。
一个对数算法不可能关注输入的每一个部分 扫描规模为n的列表 分治算法 两重嵌套循环
三重嵌套循环
16
下列等式哪些是正确的?哪些是错误的?
A. B. C. D. n(n+1)/2=O(n3) n(n+1)/2=O(n2) n(n+1)/2=θ(n3) n(n+1)/2=?(n)
17
18
题目
? 求n元中的最大元MAX(n)和最小元MIN(n)
学习目的
? 理解算法的评价方法 ? 体会算法设计及算法改进
19
void MAXMIN1(int L[], int n){ int MAX = L[1], j; for(int
i=2;i<=n;i++){ if(MAX for(int i=2;i 算法讨论: 算法讨论: 1.算法是正确的; 2.以元素之间的比较为基本操作,则求 MAX的代价是n-1,求MIN的代价是n-2 ,故总时间是2n-3 3.算法的代价只与L的长度n有关,而与L 的具体元素没有关系,故 T(n)=W(n)=A(n)=2n-3,亦可记为 T(n)=O(n)或T(n)=θ(n) 4.空间消耗除了L之外只需几个单元 S(n)=O(1) 算法思考: 算法思考: 从n元中求最大元用n-1次比较是最优的 ,从剩下的n-1元中求最小元用n-2次比 较也是最优的,但是把二者结合起来用 2n-3次比较求最大元和最小元是否是最 优的呢? 20 void MAXMIN2(int L[], int n){ int MAX=L[1], MIN=L[1]; for(int i=2;i<=n;i++){ if(MAX 算法讨论: 算法讨论: 1.把MAX和MIN放在一起处理; 2.算法总时间是2n-2,所以从效率上来说 没有任何改进 算法思考: 算法思考: 从算法结构可以很容易的看到其不合理的 地方:如果MAX 21 void MAXMIN(int L[], int n){ int MAX=L[1], MIN=L[1]; for(int i=2;i<=n;i++){ if(MAX 算法讨论: 算法讨论: 1.算法的时间代价与L[1„n]的内容有关: L[1„n] 为递增序列,需要n-1次比较, L[1„n] 为递减序列,需要2n-2次比较; 2.显然最好情形B(n)=n-1,最坏情形 W(n)=2n-2,平均情形时间复杂度A(n)难 以计算,但估计应该介于二者之间,且有 A(n)<2n-3 22 void MAXMIN(int L[], int n, int M1, int M2){ if(n==2){ if(L[1]>L[2]){ 算法讨论: 算法讨论: M1=L[1];M2=L[2]; 1.算法是针对n=2k设计的,同时可以 } 扩展到n为一般正整数的情况; else{ 2.算法的时间代价与L[1„n]的内容无 M1=L[2];M2=L[1]; 关,T(n)=1.5n-2比较原来有较大改进 } 3.基本思想是每一次比较都有助于求 } 最大元和最小元 else{ T (n) = T (n / 2) + T (n / 2) + 2 Divide L into L1 and L2; = 2(2T (n / 4) + 2) + 2 MAXMIN(L1,n/2,M11,M21); k ?1 k ?1 MAXMIN(L2,n/2,M12,M22); = 2 T ( 2) + 2 i M1=MAX(M11,M12); i =1 M2=MIN(M21,M22); = 2 k ?1 + 2 k ? 2 } 3n } = ?2 ∑ 2 23 24 排序 ? ? ? ? ? 是人们对数据集合最常用的基本操作之一 通讯录或电话本中记录一般按照人名的字典顺序排列 打牌时按牌色和点数排列 体育比赛的获奖情况按实际成绩排序 所有计算机工作中,排序占25%以上 25 全序集 ? 两个元素一定存在大小关系并且具有传递性 排序问题 ? n项纪录的集合R,其中一个域是关键字Key属于全序集, 利用Key的顺序对R重新排列 稳定排序算法 ? 相同大小的元素不被交换的算法 内部排序算法 外部排序算法 原址排序算法