tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 其它课程 >>

算法第二章


计算机算法设计与分析
Design and Analysis of Computer Algorithms
吉林大学 王生生

第二章:导引与基本数 据结构

2

第二章 导引与基本数据结构
?2.1 算法(概念) ?2.2 分析算法

?2.3 用SPARKS语言

写算法(略)
?2.4 基本数据结构 (略)

3

计算的数学本质
? 图灵机是计算机的数学原型 ? 算法的计算能力和图灵机在数学上是等价的

4

2.1 算 法
一、什么是算法
算法
数值计算方法 求解数值问题,插值计算、数值积分等

非数值计算方法 求解非数值问题,主要进行判断比较 算法属于难于定义的概念 算法的非形式描述:算法就是一组有穷的规则, 它规定了解决某一特定类型问题的一系列运算。

5

2.1 算 法
二、算法的五个重要特性
算法(Algorithm) ? 确定性 每一种运算必须要有确切的定义,无二义性 ? 能行性 运算都是基本运算,原理上能在有限时间内完成 ? 输入 有0个或多个输入 ? 输出 一个或多个输出 ? 有穷性 在执行了有穷步运算后终止
仅仅有穷还不够,还要在现代计算机上有效才行

6

程序(Program)(计算过程)
程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(5)有穷性。 例如操作系统,是一个在无限循环中执行的程序,因

而不是一个算法。
操作系统的各种任务可看成是单独的问题,每一个问 题由操作系统中的一个子程序通过特定的算法来实现。 该子程序得到输出结果后便终止。 程序 = 算法 + 数据结构 (By Niklaus Wirth )
7

2.1 算 法
三、算法学习的五个内容
? 如何设计算法
运用一些基本设计策略规划算法

? 如何表示算法
用恰当的方式表示算法

? 如何确认算法
算法正确性的证明(算法确认algorithm validation)

? 如何分析算法
通过时间和空间复杂度的分析,确定算法的优劣

? 如何测试程序
测试程序是否会产生错误的结果

8

2.2 分 析 算 法
一、如何分析算法
? 分析算法的目的
设计更高效的算法

? 算法分析的前提
要求独立于具体的软硬件环境单纯分析算法 一台通用计算机(理想情况下) 顺序处理、每次一条指令、存储容量足够大、 存取时间恒定

9

2.2 分 析 算 法
一、如何分析算法
? 算法分析的准备: ? 首先确定使用哪些运算以及执行这些运算所用 的时间。(运算包括基本运算和由一些更基本的任意
长序列的运算所组成的复杂运算)
?

其次是要确定出能反映算法在各种情况下工作 的数据集。(即要求我们编造出能产生最好、最坏
和有代表性情况的数据配置,通过使用这些数据来运 行算法,以更了解算法的性能)

10

2.2 分 析 算 法
二、全面分析算法的两个阶段
?

事前分析(a prior analysis)
? ?

求出该算法的一个时间限界函数 事前分析只限于每条语句的频率计数(frequency count) 语句的执行次数,与所用的机器无关,且独立于程序 设计语言,可由算法直接确定

?事后测试(a
?

posterior testing)

收集此算法的实际执行时间和占用空间的统计资料

11

2.2 分 析 算 法
例:计算语句x?x+y在下面三个程序段中的频率计数 begin for i?1 to n do for j?1 to n do x?x+y end FC:1 FC:n FC:n2 ?语句的数量级是指执行它的频率计数之和 begin x?x+y end ?算法的数量级是指算法的所有语句的频率计数之和
确定一个算法的数量级十分重要,因为它在本质上反映 了算法所需的计算时间。准确分析出一个算法的计算时间有 时是很困难的,因此我们对算法的计算时间进行渐进表示。
12

begin for i?1 to n do x?x+y end

算法复杂性分析形式化表述

算法复杂性即算法所需要的计算机资源
算法的时间复杂性T(n);

算法的空间复杂性S(n)。
其中n是问题的规模(输入大小)。

13

算法的时间复杂性
(1)最坏情况下的时间复杂性

Tmax(n) = max{ T(I) | size(I)=n }
(2)最好情况下的时间复杂性

Tmin(n) = min{ T(I) | size(I)=n }
(3)平均情况下的时间复杂性

Tavg(n) =

size ( I ) ? n

? p(I )T (I )

其中I是问题的规模为n的实例,p(I)是实 例I出现的概率。
14

2.2 分 析 算 法
三、计算时间的渐进表示
T(n) ?? , 当 n?? ; (T(n) - t(n) )/ T(n) ?0 ,当 n??; t(n)是T(n)的渐近性态,为算法的渐近复杂性。

在数学上, t(n)是T(n)的渐近表达式,是T(n)略去低阶
项留下的主项。它比T(n) 简单。

15

2.2 分 析 算 法
三、计算时间的渐进表示
?

定义2.1: 如果存在两个正常数c和n0, 对于所有的n≥n0,有|f(n)|≤c|g(n)| 则记作:f(n)=O(g(n))
g(n)是在事前分析中确定的某个形式的简单函数 f(n)与机器和语言有关, 而g(n)是独立于机器和语言的

Note:f(n)表示算法的计算时间,n是输入或输出量

一个算法具有O(g(n))的计算时间是指如果这个算法用n值不 变的同一类数据在某台机器上运行时,所用的时间总是小于 |g(n)|的一个常数倍。
?
?

g(n)是计算时间f(n)的一个上界函数,f(n)的数量级就是g(n)
16

|f(n)|≤c|g(n)| f(n)=O(g(n))
f(n)

17

? O 函数举例 ? 反例
证明 n3 ? O(n2) 如不然, 则存在 C 和 N 使得

当n ? N时 ,有 n3 ? Cn2 即 n ? C
显然当 n ? max{ N,C } + 1 时不成立。 所以, n3 ? O(n2)

18

2.2 分 析 算 法
定理2.1: 若A(n)=amnm+…+a1n+a0是一个m次 多项式,则A(n)=O(nm)
证明:取n0=1,当n≥n0时 由A(n)的定义和不等式关系|A+B| ≤ |A|+|B|

|A(n)| = |amnm+…+a1 n+a0 | ≤ |am|nm+…+|a1 | n+|a0 | = (|am|+|am-1|/n …+|a0 |/nm ) nm ≤ (|am|+|am-1|…+|a0 |) nm 取 c= |am|+|am-1|…+|a0 |,有|A(n)| ≤c nm 即:A(n)=O(nm),定理得证。

19

2.2 分 析 算 法

? 定理2.1表明,变量n的最高阶数为m的任一多项式, 与nm同阶。 因此一个计算时间为m阶多项式的算法,其时间 都可以用O(nm)来表示。

? 若一个算法有数量级为c1nm1,c2nm2,… cknmk的 k个语句,则算法的数量级及计算时间就是

c1nm1+c2nm2+…+cknmk=O(nm) 其中 m=max{mi|1≤ i≤ k}
20

2.2 分 析 算 法
数量级对算法有效性影响的实例 从计算时间上可把算法分为两类:
? 多项式时间算法(polynomial time algorithm):

用多项式来对其计算时间限界的算法

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
? 指数时间算法(exponential time algorithm): 计算时间用指数函数限界的算法

O(2n)<O(n!)<O(nn)
21

2.2 分 析 算 法
?定义2.2: 如果存在两个正常数c和n0, 对于所有的n≥n0,有|f(n)|≥ c|g(n)| 则记作:f(n)=Ω(g(n)) 这种情况称g(n)是计算时间f(n)的一个下界函数 在某些情况下,可能会出现g(n)既是f(n)的上界又是 它的下界,为此引入数学符号Θ来表示 ?定义2.3:如果存在两个正常数c1,c2和n0, 对于所有的n≥n0, 有 c1 |g(n)|≤ |f(n)|≤ c2 |g(n)| 则记作:f(n)=Θ(g(n))
22

|f(n)|≥ c|g(n)| f(n)=Ω(g(n))
f(n)

23

c1 |g(n)|≤ |f(n)|≤ c2 |g(n)| f(n)=Θ(g(n))
f(n)

24

Notes:补充定义
非紧上界函数o

o(g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得
对所有n? n0有:0 ? f(n)<cg(n) } 等价于 f(n) / g(n) ?0 ,as n??。 非紧下界函数?

? (g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得
对所有n? n0有:0 ? cg(n) < f(n) } 等价于 f(n) / g(n) ?? ,as n??。 f(n) ? ? (g(n)) ? g(n) ? o (f(n))
25

渐近表示函数在等式和不等式中的意义
f(n)= ?(g(n))的确切意义是:f(n) ? ?(g(n))。 一般情况下,等式和不等式中的渐近记号?(g(n))表示

?(g(n))中的某个函数。
例如:2n2 + 3n + 1 = 2n2 + ?(n) 表示 2n2 +3n +1=2n2 + f(n),其中f(n) 是?(n)中某个函数。 等式和不等式中渐近记号O,o, ?和?的意义是类似的。

26

渐近分析中函数比较
a=f(n); b= C g(n)

f(n)= O(g(n)) ? a ? b;
f(n)= ?(g(n)) ? a ? b;

f(n)= ?(g(n)) ? a = b;
f(n)= o(g(n)) ? a < b; f(n)= ?(g(n)) ? a > b.

27

渐近表示函数的若干性质
(1)传递性: f(n)= ?(g(n)), g(n)= ?(h(n)) ? f(n)= ?(h(n));

f(n)= O(g(n)), g(n)= O (h(n)) ? f(n)= O (h(n));
f(n)= ?(g(n)), g(n)= ? (h(n)) ? f(n)= ?(h(n));

f(n)= o(g(n)), g(n)= o(h(n)) ? f(n)= o(h(n));
f(n)= ?(g(n)), g(n)= ? (h(n)) ? f(n)= ? (h(n));
28

(2)反身性: f(n)= ?(f(n)); f(n)= O(f(n)); f(n)= ?(f(n)).

(3)对称性:
f(n)= ?(g(n)) ? g(n)= ? (f(n)) .

(4)互对称性:
f(n)= O(g(n)) ? g(n)= ? (f(n)) ; f(n)= o(g(n)) ? g(n)= ? (f(n)) ;
29

(5)算术运算: O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ; O(f(n))+O(g(n)) = O(f(n)+g(n)) ;

O(f(n))*O(g(n)) = O(f(n)*g(n)) ;
O(cf(n)) = O(f(n)) ;

g(n)= O(f(n)) ? O(f(n))+O(g(n)) = O(f(n)) 。
? ? 也有类似性质,证明方法类似

30

规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明:
对于任意f1(n) = O(f(n)) ,存在正常数c1和自然数n1,使得对所有
n? n1,有f1(n) ? c1f(n) 。 类似地,对于任意g1(n) = O(g(n)) ,存在正常数c2和自然数n2,

使得对所有n? n2,有g1(n) ? c2g(n) 。
令c3=max{c1, c2}, n3 =max{n1, n2},h(n)= max{f(n),g(n)} 。 则对所有的 n ? n3,有 f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)= c3(f(n) + g(n))

? 2c3 max{f(n),g(n)}
= 2c3h(n) = O(max{f(n),g(n)}) .

31

规则O(f(n))+O(g(n)) = O(f(n)+g(n)) 的证明:
对于任意f1(n) = O(f(n)) ,存在正常数c1和自然数n1,使得对所有 n? n1,有f1(n) ? c1f(n) 。 类似地,对于任意g1(n) = O(g(n)) ,存在正常数c2和自然数n2, 使得对所有n? n2,有g1(n) ? c2g(n) 。 令c3=max{c1, c2}, n3 =max{n1, n2},h(n)= f(n)+g(n) 。 则对所有的 n ? n3,有

O(f(n))+O(g(n)) =
f1(n) +g1(n) ? c1f(n) + c2g(n) ? c3f(n) + c3g(n)= c3(f(n) + g(n))

=c3h(n) = O(f(n)+g(n)) .

32

规则O(f(n))*O(g(n)) = O(f(n)*g(n)) 的证明:
对于任意f1(n) = O(f(n)) ,存在正常数c1>1和自然数n1,使得对所有
n? n1,有f1(n) ? c1f(n) 。 类似地,对于任意g1(n) = O(g(n)) ,存在正常数c2>1和自然数n2,

使得对所有n? n2,有g1(n) ? c2g(n) 。
令c3=c1*c2, n3 =max{n1, n2},h(n)= f(n)*g(n) 。 则对所有的 n ? n3,有

O(f(n))*O(g(n)) =
f1(n) *g1(n) ? c1f(n) * c2g(n)

= c3f(n)*g(n) =c3h(n) = O(f(n)*g(n)) .

33

算法分析中常见的复杂性函数

34

小规模数据

35

中等规模数据

36

不同时间复杂性函数的对比

37

2.2 分 析 算 法
四、常用的整数求和公式
1?i ? n

?1 ? ?(n)
2

1?i ?n

?i ? n(n ?1) / 2 ? ?(n )
2

1?i ?n

?i

? n(n ? 1)(2n ? 1) / 6 ? ?(n )
k ?1 k

3

n n ? ? 通式: ?i k ?1 2
k 1?i ?n

? 低次项 ? ?(n )

k ?1

38

? 时空性能分布图
算法时间的准确测量

时钟不准确造成的噪声
解决方法

增大规模
重复执行 分布图的做法

39

2.3 用SPARKS语言写算法
?SPARKS语言的基本数据类型:
整型(integer), 实型(real), 布尔型(boolean), 字符型(char)

例: integer x, y; char ch; 布尔值: True,False ?SPARKS语言的变量命名规则:
以字母开头,不允许使用特殊字符,不允许与保留字重复

?赋值语句:变量 ? 表达式 ?逻辑运算符:and , or , not ?关系运算符:< ,≤,=,≠,>, ≥ ?数组:任意整数下界和上界的多维数组 例: integer A(1:10); real B(1:3 , 1:4);
40

2.3 用SPARKS语言写算法
?SPARKS语言的条件语句 if 条件 then s1 ? if (条件) { s1 } endif if 条件 then s1 ? if (条件) { s1 } else s2 else { s2 } endif ?SPARKS语言的case语句 case case 条件 1: s1 : 条件 1: s1 … … ? 条件 n: sn : 条件 n: sn else : sn+1 : else : sn+1 endcase endcase
41

2.3 用SPARKS语言写算法
?SPARKS语言的循环语句 while 条件 do S repeat loop S until 条件 repeat while (条件) { S} do {S} while ( 条件 )

for 变量?初值 to 终值 by 变量增值 do S for (变量=初值;循环条件;变量增值 ) repeat {S}
42

2.3 用SPARKS语言写算法
?SPARKS语言的输入、输出: read(参数表);print(参数表); ?SPARKS语言的函数(过程) procedure NAME(<参数列表>)
<说明部分>
说明参数的数据类型 和函数中使用的变量 parameters 形式参数 global 全局变量 local 局部变量 函数名,通常用大写字母

S

函数的语句部分

return(<表达式>) end NAME

43

2.3 用SPARKS语言写算法
procedure MAX(A, n, j) parameters real A(1:n); parameters integer n, j; real xmax; local integer i; xmax?A(1); for i?2 to n do if A(i)>xmax then xmax?A(i); j?i; endif repeat return(xmax); end MAX procedure MAX(A, n, j) float A(1:n); int n, j; global float xmax; int i; xmax=A[1]; for( i=2; i<=n; i++) if (A[i]>xmax) { xmax=A[i]; j=i; } return(xmax); end MAX

44

2.4.3 集合的树结构表示
针对只有查找和合并操作的不相交集合

? 集合的表示方法1
位向量表示: 交并操作:位运算 空间占用太多

45

2.4.3 集合的树结构表示 ? 集合的表示方法2
元素表表示: 交并操作: 无序: 交并 O(mn) 判断属于O(n) 有序: 不妨假定元素互不相同 并:O(m+n) 【Merge】 交:O(m+n) 【一次扫描】 判断属于O(log(n)) 【二分检索】 树结构表示: 并操作的实现
46

2.4.3 集合的树结构表示 ? 集合的表示方法3
树结构表示: 能表示不相交集合(无交操作) 数据结构(举例) 树(非二叉树) 只有父指针(数组模拟)、无儿子指针 并操作的实现(举例)

47

48

49

50

小结
算法的五个重要特性
确定性、可行性、输入、输出、有穷性

学习算法的五个内容 算法分析的基本概念和思想 算法时间复杂度的渐进表示 了解意义、会使用、能推导证明性质

51


推荐相关:

算法导论第二章答案

此笔记尚未定稿 如果问题和建议请联系 zhangshuijing @msn.com 欢迎指教 第二章 算法入门由 于时 间问题 有些 问题没 有写的 很仔 细,而 且估 计这里 会...


最优化理论与算法(第二章)

最优化理论与算法(第二章)_理学_高等教育_教育专区。最优化理论笔记第二章 一维搜索 §2.1. 引言 一、精确与非精确一维搜索 如前所述,最优化算法的迭代格式为...


必修3 第二章算法教案

必修3 第二章算法教案_高一数学_数学_高中教育_教育专区。富县高级中学集体备课教案年级:高一 课题 科目: 数学第一节 算法的基本思想 授课人: 第 1 课时 1....


选修3第二章算法

选修3第二章算法_数学_高中教育_教育专区。学思教育 高一数学◆必修 3◆ 日期: 姓名: 算法初步一、 算法概念: 1, 算法特征: 2, 算法流程: 3, 算法框图: ...


算法导论第二章第一节答案

算法导论第二章第一节答案_工学_高等教育_教育专区。算法导论第二章第一节课后习题详细答案讲解2.1-2 重写过程 INSERTION-SORT,使之按非升序(而不是按非降序...


第一章&第二章算法题

算法_前言、第一章、第二章... 71页 免费 数据结构及应用算法教程习... 6页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...


第二章 算法与程序设计

第二章 算法与程序设计“算法与程序设计”是高中信息技术课程的选修模块,以问题解决与程序设计为主线, 揭示利用计算机解决问题的过程。学生通过本模块的学习“体验...


第二章 计算方法和运算器(十一)

3. 4. 教学重点 教学难点 教学时数 教学内容: 第二章 计算方法和运算器(十一) 2.6.1 多功能算术/逻辑运算单元(ALU) 我们曾介绍由一位全加器(FA)构成的...


计算方法第二章作业答案参考

计算方法第二章作业答案参考_财会/金融考试_资格考试/认证_教育专区。习题二 1. 用二分法求方程 x ? 3x ? 1 ? 0 在区间【0.3,0.4】内的根,要求误差不...


第二章 计算方法和运算器(十二)

3. 教学重点 教学难点 教学时数 教学内容: 第二章 计算方法和运算器(十二) 2.6.2 内部总线 所谓总线,就是一个或多个信息源传送信息到多个目的的数据通路,...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com