2010-5-14 计算机算法设计与分析 1
计算机算法
设计与分析
信息工程学院周经野
电话,8292350
2010-5-14 计算机算法设计与分析 2
第一章
算法概述
2010-5-14 计算机算法设计与分析 3
算法与过程
? 过程 (Procedure)与算法 (Algorithm)是解决问题
的一种方法的逐步描述，它
? (1)是由若干条指令组成的有穷序列；
? (2)每条指令的意义都是确定的；
? (3)具有零个或多个输入；
? (4)产生若干个输出；
? 算法要求其 (5)执行时间是有限的 (终止性 ) 。
? 过程的执行时间可能是无限的。
2010-5-14 计算机算法设计与分析 4
程序
? 程序是某个算法或过程的在计算机上的
一个具体的实现。
? 程序是依赖于程序设计语言的，甚至依
赖于计算机结构的。
? 算法是脱离具体的计算机结构和程序设
计语言的。
2010-5-14 计算机算法设计与分析 5
算法的复杂性
? 算法的复杂性是指算法运行时所需要的
计算机资源的量多少，所需资源量越多
则复杂性越高，反之所需资源量越少则
复杂性越低。其中最为重要的是：
? 时间复杂性：需要时间的资源量。
? 空间复杂性：需要空间的资源量。
? 这里人们通常更为关注的是时间复杂性。
2010-5-14 计算机算法设计与分析 6
决定算法复杂性的因素
? 算法的复杂性取决于
? (1)求解问题的规模；
? (2)具体的输入数据；
? (3)算法本身的设计。
? 若 令 N,I,和 A分别表示问题的规模、具体的
输入和算法本身，则
C = F(N,I,A)
或 C = FA(N,I) = F( N,I)
2010-5-14 计算机算法设计与分析 7
时间复杂性的计算
? 时间 复杂性 T(N,I)的计算为：
? 其中：
? ti为执行抽象计算机的第 i种指令一次所需要的
时间，这里假定抽象计算机共有 k种指令。
? ei(N,I)为经过统计后得到的 执行抽象计算机的
第 i种指令的次数。
k
T(N,I) = ? ti ei(N,I)
i = 1
2010-5-14 计算机算法设计与分析 8
最坏、最好或平均的情况
? 令,D为规模为 N的合法输入的集合；
I*表示在最坏情况下的输入；
I#表示在最好情况下的输入；
P(I)输入 I出现的概率。
? W(N) = max I?DT(N,I) = T(N,I*)
? B(N) = min I?DT(N,I) = T(N,I#)
? A(N) = ? I?DP(I)T(N,I)
? 三者中最常用的是 W(N) 。
2010-5-14 计算机算法设计与分析 9
复杂性分析的简化
? 令 T(N)为表示算法 A的复杂性函数，若存在 ? (N)，
使得
Lim N?? (T(N) –?(N)) / T(N) = 0
那么，就可以用 ?(N)来代替 T(N), 从而简化复杂
性的分析。
? 例如,T(N) = 3N2+4NlogN+7,?(N) = 3N2,则
Lim N?? (T(N) –?(N)) / T(N)
= Lim N?? 4NlogN+7 / 3N2+4NlogN+7 = 0
2010-5-14 计算机算法设计与分析 10
用阶来表示复杂性
? 在渐进复杂性分析中，只要关心 ?(N)的
阶就够了，不必关心 ?(N)中的常数因子，
这样我们就只需要用 ?(N)的阶来表示该
算法的复杂性。
? 例如，计算一个 N维矩阵 A的平方的时间
复杂性可估算为 2N*N2 = 2N3,即此计算
的时间复杂性为 3阶。
2010-5-14 计算机算法设计与分析 11
几个记号
? 设 f(N),g(N)都是定义在正整数集上的函数。
? 上界记号 O,如果存在正的常数 C和自然数 N0，
使得当 N≧ N0 时有 f(N)≦ Cg(N),则 f(N)有上
界函数 g(N),记为 f(N) = O(g(N))。
? 下界记号 Ω,如果存在正的常数 C和自然数 N0，
使得当 N≧ N0 时有 f(N)≧ Cg(N),则 f(N)有下
界函数 g(N),记为 f(N) = Ω(g(N))。
? 同阶记号 Θ,f(N)= Θ(g(N))表示 f(N)和 g(N)同
阶 。
? 低阶记号 o,f(N)=o(g(N))表示 f(N)比 g(N)低阶
2010-5-14 计算机算法设计与分析 12
常用的算法设计技术
? 分治法 (Divide and Conquer)
? 动态规划法 (Dynamic Programming)
? 贪心法 (Greedy)
? 回溯法 (Backtracking)
? 分支界限法 (Branch and Bound)
? 这些算法中都使用了递归 (Recursion)。
计算机算法
设计与分析
信息工程学院周经野
电话,8292350
2010-5-14 计算机算法设计与分析 2
第一章
算法概述
2010-5-14 计算机算法设计与分析 3
算法与过程
? 过程 (Procedure)与算法 (Algorithm)是解决问题
的一种方法的逐步描述，它
? (1)是由若干条指令组成的有穷序列；
? (2)每条指令的意义都是确定的；
? (3)具有零个或多个输入；
? (4)产生若干个输出；
? 算法要求其 (5)执行时间是有限的 (终止性 ) 。
? 过程的执行时间可能是无限的。
2010-5-14 计算机算法设计与分析 4
程序
? 程序是某个算法或过程的在计算机上的
一个具体的实现。
? 程序是依赖于程序设计语言的，甚至依
赖于计算机结构的。
? 算法是脱离具体的计算机结构和程序设
计语言的。
2010-5-14 计算机算法设计与分析 5
算法的复杂性
? 算法的复杂性是指算法运行时所需要的
计算机资源的量多少，所需资源量越多
则复杂性越高，反之所需资源量越少则
复杂性越低。其中最为重要的是：
? 时间复杂性：需要时间的资源量。
? 空间复杂性：需要空间的资源量。
? 这里人们通常更为关注的是时间复杂性。
2010-5-14 计算机算法设计与分析 6
决定算法复杂性的因素
? 算法的复杂性取决于
? (1)求解问题的规模；
? (2)具体的输入数据；
? (3)算法本身的设计。
? 若 令 N,I,和 A分别表示问题的规模、具体的
输入和算法本身，则
C = F(N,I,A)
或 C = FA(N,I) = F( N,I)
2010-5-14 计算机算法设计与分析 7
时间复杂性的计算
? 时间 复杂性 T(N,I)的计算为：
? 其中：
? ti为执行抽象计算机的第 i种指令一次所需要的
时间，这里假定抽象计算机共有 k种指令。
? ei(N,I)为经过统计后得到的 执行抽象计算机的
第 i种指令的次数。
k
T(N,I) = ? ti ei(N,I)
i = 1
2010-5-14 计算机算法设计与分析 8
最坏、最好或平均的情况
? 令,D为规模为 N的合法输入的集合；
I*表示在最坏情况下的输入；
I#表示在最好情况下的输入；
P(I)输入 I出现的概率。
? W(N) = max I?DT(N,I) = T(N,I*)
? B(N) = min I?DT(N,I) = T(N,I#)
? A(N) = ? I?DP(I)T(N,I)
? 三者中最常用的是 W(N) 。
2010-5-14 计算机算法设计与分析 9
复杂性分析的简化
? 令 T(N)为表示算法 A的复杂性函数，若存在 ? (N)，
使得
Lim N?? (T(N) –?(N)) / T(N) = 0
那么，就可以用 ?(N)来代替 T(N), 从而简化复杂
性的分析。
? 例如,T(N) = 3N2+4NlogN+7,?(N) = 3N2,则
Lim N?? (T(N) –?(N)) / T(N)
= Lim N?? 4NlogN+7 / 3N2+4NlogN+7 = 0
2010-5-14 计算机算法设计与分析 10
用阶来表示复杂性
? 在渐进复杂性分析中，只要关心 ?(N)的
阶就够了，不必关心 ?(N)中的常数因子，
这样我们就只需要用 ?(N)的阶来表示该
算法的复杂性。
? 例如，计算一个 N维矩阵 A的平方的时间
复杂性可估算为 2N*N2 = 2N3,即此计算
的时间复杂性为 3阶。
2010-5-14 计算机算法设计与分析 11
几个记号
? 设 f(N),g(N)都是定义在正整数集上的函数。
? 上界记号 O,如果存在正的常数 C和自然数 N0，
使得当 N≧ N0 时有 f(N)≦ Cg(N),则 f(N)有上
界函数 g(N),记为 f(N) = O(g(N))。
? 下界记号 Ω,如果存在正的常数 C和自然数 N0，
使得当 N≧ N0 时有 f(N)≧ Cg(N),则 f(N)有下
界函数 g(N),记为 f(N) = Ω(g(N))。
? 同阶记号 Θ,f(N)= Θ(g(N))表示 f(N)和 g(N)同
阶 。
? 低阶记号 o,f(N)=o(g(N))表示 f(N)比 g(N)低阶
2010-5-14 计算机算法设计与分析 12
常用的算法设计技术
? 分治法 (Divide and Conquer)
? 动态规划法 (Dynamic Programming)
? 贪心法 (Greedy)
? 回溯法 (Backtracking)
? 分支界限法 (Branch and Bound)
? 这些算法中都使用了递归 (Recursion)。
