需要多少时间?
15
解 实例大小为n, 则 n3 = 3600·1000 n = 153
用A2需要时间为 n2 = 1532 = 23489 毫秒 = 23
秒
16
如原来算法的复杂度T (n)＝ 2n ，则 2n = 3600 × 1000 问题实例大小
n = log 2 (3600 × 1000) ＝22
显然, c·f(n)是T(n)的上界.
千万注意: 不可写成 O(f(n)) = T(n)
18
例如 4n3 = O(n3) 2n3 = O(n3) 7n3 + 5n + 1000 = O(n3)
若T(n)是多项式, 用大O标记时, 只与最高 项次数有关, 与其系数无关, 与低次项无 关.
19
大O记号将复杂度表达式简单化了， 但最本质的东西被保留了。因此用来表 示算法复杂度的数量级。
1秒
1分
1小时
1000n
1
60
3600
10 n2
10
77
600
2n
10
16
22
1000n = 3600 × 1000, n = 3600
2n = 3600 × 1000
n= log 2 (3600×1000) = log 2 3.6 + log 2 1000 + log 2 1000= 22
13
不同计算机对问题实例大小的限制
24
§2. 算法分析
25
A. 正确性 给定实例任何有效的输入 数据后, 算法经过有限时间的运算 给出实例的结果.
正确性的证明不是容易的事情. 一般地，将整个算法分成部分, 各个
部分完成原问题的子任务, 证明了各部分的正确性,合起来就证
明了整个算法的正确性.
26
B. 复杂度 取决于工作量. 工作量的度量应
❖ 空间复杂度 ❖ 处理器复杂度
11
实例大小一定时所需时间(ms)
算法 A1 A3
实
复杂度
2
例大 10
小 60
1000n 2000Fra bibliotek104
6·104
2n
4
103
1018
复杂度单位是毫秒
1018 = 1015秒= 1015 /3600/24/365 年 > 107年
12
规定时间内可处理的最大实例
复杂度
20
如果 T(n) = O(nk), 则有 T(n) = O(n j) (j > k) 若求复杂度的大O(nk)表示, 应当求出
k的最小值
21
定义 两个非负函数T(n)和g(n)定义在非负整数上， 如存在正数c，使T(n) ≧ c·g(n) 对无穷多的n取值成立。则记为
T(n)＝Ω (g(n)) 要注意的是，g(n)并不是T(n)的下界。
9
❖ 算法A的时间复杂度(n的函数)定义为
TA(n) =max{m|存在实例x, |x|=n, A对 x
运行所需时间为m}
❖ 时间复杂度就是算法A对大小为n的所有实例 运行所需时间的最大者.
❖ 此即, 最坏情况
❖ 因此，时间复杂度是n的函数.
10
❖我们主要关心时间复杂度, 说 到复杂度主要就是指时间复杂 度.
4
对算法的要求 ❖易于理解：易于编程 易于调试 ❖高效：时间上快 存储空间小
这两者是互相矛盾的 ❖高效的算法往往不易于理解、编程、
调试 ❖易于理解、编程、调试的算法往往
低效
5
❖ 如何选择 取决于实际需求
❖只运行一两次的程序, 不必高效, 易 于编程即可
❖多次反复运行的程序, 则要求高效, 宁可编程时候多花费时间, 但将来 多次运行可以节省大量时间
6
❖以排序问题为例子。 ❖汽泡法最直观简单，但时间要求
最长； ❖快速排序法快一点，但是其思路
不是那么易懂； ❖堆排序最快，可是它的思路更加
难懂。
7
算法或由它写成的程序运行所需要的时间决 定于两个因素：
❖问题实例的大小 ❖实例的具体情况
8
❖问题的实例用x 表示， ❖实例的大小用|x|表示， ❖算法所需要的时间不仅与|x|有关。
用算法A2则需时间 n 2 = 22 2＝484毫秒 ＝0．4秒 (一瞬间) 由此可见改进算法复杂度意义重大。
17
定义 两个非负函数T(n)和f(n)定义在非 负整数域, 如存在正数c和正整数N, 使 得 T(n) ≤ c·f(n) (n ≥ N)
则称T(n)的阶小于或等于f(n)的阶, 记作 T(n) = O(f(n))
22
例 T(n) = n , n 为奇数 T(n) = n2 /100, n 为偶数
显然有 T(n) = Ω (n2), 只要令c = 1/100 但是n2不是T(n)的下界
23
如果 T(n) = Ω(nk), 则有 T(n) = Ω(n j) (j < k)
若求复杂度的大O(nk)表示, 应当求出 k的最大值
❖ 算法为问题而建立，但是算法不能 为问题而运行；
❖ 算法只能为问题的实例而运行。
2
算法的特性为有穷性
❖有限序列 ❖有限工作量 ❖有限时间，这一点更要强调
3
❖专业人才不仅注意算法设计的技 巧，更注重算法运行所需的时间 和存储空间
❖更应当分析算法的品性。 ❖一个问题往往有多个算法，
❖评判比较解决同一问题的各种不 同算法优劣的标准。
与使用的计算机无关, 与编程的语言无关.
用运行时间做度量或执行的指令数目做度 量, 都不适宜.
选取基本运算, 计其执行次数,以此作为工 作量. 优点: 便于比较同一问题的不同算 法.
选取的基本运算多, 则工作量度量越精确, 但分析越复杂;
反之, 分析简单, 但是, 工作量度量就粗糙.
27
选取基本运算, 只计算基本运算的执行次数.
§1. 算法的复杂度
算法的定义: 问题的算法是有限条指令的序列, 其中每条指令都有明确的含义, 每条指令的执行包含着有限的工作量, 序列的执行会在有限时间内停止下来, 并给出问题实例的解答.
1
❖ 问题: 一个一般化的概念. 例如: 排序 问题
❖ 实例: 问题的一个实际情况. 例如, 排 序问题中待排序的量的个数、每个 量的值构成了问题的一个实例。
复杂度
原机器
新机器
1000n
S
10S
2n
S
S+3
新机器的性能是原机器的10倍. 设新机器可处理的问题大小为S’ 1000S’ = 1000S × 10 S’ = 10 S
2S’ = 2S × 10
S’ = S + log 2 10 = S + 3
14
❖问题P有算法A1，复杂度T1(n)= n3
❖现在把算法改善为A2, ❖复杂度T2(n)= n2, ❖原来要1小时运行时间的实例现在