计算机算法 设计与分析 信息工程学院周经野 电话:8292350 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 计算机算法 设计与分析 信息工程学院周经野 电话：8292350
第一章 算法述 2021/2/21 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 第一章 算法概述
算法与过程 ■过程( Procedure)与算法( Algorithm)是解决问题 的一种方法的逐步描述,它 (1)是由若干条指令组成的有穷序列 ■(2)每条指令的意义都是确定的; (3)具有零个或多个输入; (4)产生若干个输出; 算法要求其(5)执行时间是有限的(终止性)。 ■过程的执行时间可能是无限的。 2021/221 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 算法与过程 ◼ 过程(Procedure)与算法(Algorithm)是解决问题 的一种方法的逐步描述，它 ◼ (1)是由若干条指令组成的有穷序列； ◼ (2)每条指令的意义都是确定的； ◼ (3)具有零个或多个输入； ◼ (4)产生若干个输出； ◼ 算法要求其(5)执行时间是有限的 (终止性) 。 ◼ 过程的执行时间可能是无限的
程序 ■程序是某个算法或过程的在计算机上的 个具体的实现 ■程序是依赖于程序设计语言的,甚至依 赖于计算机结构的 ■算法是脱离具体的计算机结构和程序设 计语言的。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 程序 ◼ 程序是某个算法或过程的在计算机上的 一个具体的实现。 ◼ 程序是依赖于程序设计语言的，甚至依 赖于计算机结构的。 ◼ 算法是脱离具体的计算机结构和程序设 计语言的
算法的复杂性 ■算法的复杂性是指算法运行时所需要的 计算机资源的量多少,所需资源量越多 则复杂性越髙,反之所需资源量越少则 复杂性越低。其中最为重要的是: ˉ时间复杂性:需要时间的资源量 ■空间复杂性:需要空间的资源量。 ■这里人们通常更为关注的是时间复杂性。 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 算法的复杂性 ◼ 算法的复杂性是指算法运行时所需要的 计算机资源的量多少，所需资源量越多 则复杂性越高，反之所需资源量越少则 复杂性越低。其中最为重要的是： ◼ 时间复杂性：需要时间的资源量。 ◼ 空间复杂性：需要空间的资源量。 ◼ 这里人们通常更为关注的是时间复杂性
决定算法复杂性的因素 ■算法的复杂性取决于 ■(1)求解问题的规模; (2)具体的输入数据; (3)算法本身的设计。 ■若令N、Ⅰ、和A分别表示问题的规模、具体的 输入和算法本身,则 C=F(N,L,A) 或 C=FAN, D=F(N, D 2021/22 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 决定算法复杂性的因素 ◼ 算法的复杂性取决于 ◼ (1)求解问题的规模； ◼ (2)具体的输入数据； ◼ (3)算法本身的设计。 ◼ 若令N、I、和A分别表示问题的规模、具体的 输入和算法本身，则 C = F(N, I, A) 或 C = FA(N, I) = F( N, I)
时间复杂性的计算 时间复杂性TN,D的计算为: T(N, D=2te N, D ■其中: ■t为执行抽象计算机的第种指令一次所需要的 时间,这里假定抽象计算机共有k种指令。 ■e(N,Ⅰ为经过统计后得到的执行抽象计算机的 第种指令的次数。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 时间复杂性的计算 ◼ 时间复杂性T(N, I)的计算为： ◼ 其中： ◼ t i为执行抽象计算机的第i种指令一次所需要的 时间，这里假定抽象计算机共有k种指令。 ◼ ei (N, I)为经过统计后得到的执行抽象计算机的 第i种指令的次数。 k T(N, I) = t i ei (N, I) i = 1
最坏、最好或平均的情况 ■令:D为规模为N的合法输入的集合; I*表示在最坏情况下的输入; Ⅳ表示在最好情况下的输入; P①输入I出现的概率 W(N=max(N,D=t(N,I) B(N-min edt(N,D=t(N, I) ■A(N)=∑lepP(I)T(N,I 三者中最常用的是W(N)。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 最坏、最好或平均的情况 ◼ 令：D为规模为N的合法输入的集合； I*表示在最坏情况下的输入； I #表示在最好情况下的输入； P(I)输入I出现的概率。 ◼ W(N) = max IDT(N, I) = T(N, I*) ◼ B(N) = min IDT(N, I) = T(N, I# ) ◼ A(N) = IDP(I)T(N, I) ◼ 三者中最常用的是W(N)
复杂性分析的简化 令TN)为表示算法A的复杂性函数,若存在T(N), 使得 Lim N- (T(N)-T(N/TN)=0 那么,就可以用T(N)来代替T(N),从而简化复杂 性的分析 例如:T(N)=3N2+4NogN+7,T(N)=3N2,则 Lim N- (T(N)-TIN/T(N Lim N-a 4Nlog N+7 /3N2-+4NlogN+7=0 2021/221 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 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
用阶来表示复杂性 在渐进复杂性分析中,只要关心(N的 阶就够了,不必关心T(N)中的常数因子 这样我们就只需要用TN)的阶来表示该 算法的复杂性 ■例如,计算一个N维矩阵A的平方的时间 复杂性可估算为2N*N2=2N3,即此计算 的时间复杂性为3阶。 2021/22 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 用阶来表示复杂性 ◼ 在渐进复杂性分析中，只要关心Ť(N)的 阶就够了，不必关心Ť(N)中的常数因子， 这样我们就只需要用Ť(N)的阶来表示该 算法的复杂性。 ◼ 例如，计算一个N维矩阵A的平方的时间 复杂性可估算为2N*N2 = 2N3 ，即此计算 的时间复杂性为3阶