第二章 算法分析基础
- 格式：ppt
- 大小：243.00 KB
- 文档页数：1
下载文档原格式
合集下载
算法2_算法分析基础
关键操作通常是位于算法最内层循环的程序步（或语句）， ch2.20 是算法中执行次数最多的操作（程序步） 。
（2）渐近下界记号
如果存在正常数c和自然数n0，使得当n n0时有f(n) ≥cg(n) ，则称函数f(n)当
n充分大时有下界，且g(n)是它的一个下界，记做f(n)=(g(n)) 。即f(n)的阶 不低于g(n)的阶。
//1
//1
//1
2 n0 T (n) T (n 1) 2 n 0
程序总步数为：2n+2
但递归调用引起的循环计算和使用for语句的循环计算所需的开销是不同的。递 归需要耗费更多的时间和空间资源。
可见：程序步数并不能确切反映程序运行的实际时间。
ch2.14
2.2 渐近表示法
好算法的4个重要特征： Correctness——正确性
注意区分“正确性”和“健壮性”的概念： 算法正确性——在合法的输入下，算法应实现预先规定的功能和计算精度要求。 程序健壮性——当输入不合法的数据时，程序应能做适当处理而不至于引起严 重后果。 正确性和健壮性互相补充。 程序可靠性——在正常情况下能正确地工作，在异常情况下也能做出适当处理。
表示常数计算时间，代 做f(n)=O(g(n)) 。即f(n)O(1) 的阶不高于 g(n)的阶。
表算法只需执行有限个程序 步。 上界记号O举例： 如何证明？ C0=O(1) f(n)=C 0为非零常数，取c=c0 100n+6=O(n) 取c=101, n0=6 6*2n+n2=O(n2) 取c=7, n0=4 3log n+2*n+n2=O(n2) 取c=6, n0=1
执行算法所需的时间和存储空间
算法设计者常常需要在算法的简明 性和效率之间作出谨慎的选择
《算法设计与分析基础(第3版)》第一,二章部分习题答案
作业一学号：_____ 姓名：_____说明：1、正文用宋体小四号，1.5倍行距。
2、报告中的图片、表格中的文字均用宋体五号，单倍行距。
3、图片、表格均需要有图片编号和标题，均用宋体五号加粗。
4、参考文献用宋体、五号、单倍行距，请参照参考文献格式国家标准（GB/T 7714-2005）。
5、公式请使用公式编辑器。
P144.用伪代码写一个算法来求方程ax2+bx+c=0的实根，a，b，c 是任意实系数。
（可以假设sqrt(x)是求平方根的函数。
）算法：Equate(a,b,c)//实现二元一次方程求解实数根//输入：任意系数a，b，c//输出：方程的实数根x1，x2或无解If a≠0p←b2−4acIf p>0x1←−b+sqrt(p)2ax2←−b−sqrt(p)2areturn x1，x2else if p=0return −b2aelsereturn “no real roots”elseif b≠0return −cbelseif c≠0return “no real numbers”elsereturn “no real roots”5.写出将十进制正整数转换为二进制整数的标准算法。
a.用文字描述。
b.用伪代码描述。
a.解：输入：一个正整数n输出：正整数n相应的二进制数第一步：用n 除以2，余数赋给K[i](i=0,1,2...)，商赋给n第二步：如果n=0 ，则到第三步，否则重复第一步第三步：将K[i]按照i从高到低的顺序输出b.解：算法：DecToBin(n)//实现正整数十进制转二进制//输入：一个正整数n//输出：正整数n对应的二进制数组K[0..i]i ←1while n≠0 doK[i]←n%2n←(int)n/2i ++while i≠0doprint K[i]i - -p462.请用O，Ω 和θ的非正式定义来判断下列断言是真还是假。
a. n(n+1)/2∈O(n3)b. n(n+1)/2∈O(n2)c. n(n+1)/2∈θ(n3)d. n(n+1)/2∈Ω(n)解：断言为真：a，b，d断言为假：cP535.考虑下面的算法。
算法与算法分析基础
运算（也可称为语句）
组成的运算集������ = {������1, ������2, … , ������: }
§ 每个基本运算的执行时间是有限常量 § 设执行第������ 个运算������������ 所需的
，1 ≤ ������ ≤ ������
3
2.1
q时间复杂度（time complexity）
证明：取������0 = 1，当������ ≥ ������0时，有
������(������) = ������: ������: + ������:~J ������������-1 + ! + ������1������ + ������0 £|������: |������: + |������:~J |������:~J + ! + |������1|������ + |������0| £(|������: | + |������:~J |/������ + L + |������1|/������:~J + |������0|/������: )������: £(|������: | + |������:~J | + ! + |������1| + |������0|)������: 可取������ = |������: | + |������:~J | + ! + |������1| + |������0|，定理得证。
，1 ≤ ������ ≤ ������，������������ 也是������和������ 的函数，记做������������ (������, ������)。
算法分析第2章范文
算法分析第2章范文算法分析是计算机科学中的一个重要分支，它主要研究算法的性能和效率。
在这一章中，我们将介绍一些常见的算法分析技术，包括复杂度分析和递归关系求解。
同时，我们还将介绍一些常用的算法设计技巧，如迭代和递归。
首先，我们来介绍复杂度分析。
复杂度分析是衡量算法性能的主要指标，它主要关注算法的时间复杂度和空间复杂度。
时间复杂度表示算法执行所需的时间量级，常用的时间复杂度有常数阶O(1)、对数阶O(log n)、线性阶O(n)、平方阶O(n2)等。
空间复杂度表示算法所需的额外存储空间量级，常用的空间复杂度有常数阶O(1)、线性阶O(n)等。
通过对算法的复杂度进行分析，我们可以选择最优的算法来解决问题。
接下来，我们介绍递归关系求解。
递归关系是一种描述递归算法复杂度的数学表达式，它通常用于分析递归算法的时间复杂度。
求解递归关系的方法有递归树法和主定理法。
递归树法通过绘制递归算法的运行过程形成一棵递归树，然后通过对递归树进行求和来求解递归关系。
主定理法是一种通用的求解递归关系的方法，它基于分治算法的思想，通过比较递归关系与基本情况的复杂度来求解整个递归算法的复杂度。
然后，我们介绍一些常用的算法设计技巧。
迭代是一种基本的算法设计技巧，它通过循环结构来重复执行一段代码，从而解决问题。
迭代通常用于解决需要重复操作的问题，如数组遍历和排序。
递归是一种高级的算法设计技巧，它通过调用自身的方式来解决问题。
递归通常用于解决需要反复分解的问题，如树的遍历和图的。
除了迭代和递归，还有一些其他的算法设计技巧，如分治算法、贪心算法和动态规划算法。
最后，我们讨论了算法的优化和改进。
算法的优化和改进是一个迭代的过程，它通过对算法进行深入分析和调整来提高算法的性能。
算法的优化和改进可以从多个角度入手，如减少时间复杂度、减少空间复杂度、消除重复操作等。
在进行算法优化和改进时，我们还需要考虑算法的可读性、可维护性和可扩展性。
总之，算法分析是计算机科学中的重要内容，它对于理解和设计高效的算法至关重要。
《计算机算法基础》教学大纲
《计算机算法基础》教学大纲计算机算法基础教学大纲课程简介本课程作为计算机科学与技术专业必修课，旨在让学生掌握计算机算法的基础知识和基本应用，为后续深入研究算法提供基础。
教学目标通过本课程的研究，学生将能够：- 熟练掌握常用的计算机算法- 理解各种算法的基本思想和运行原理- 能够运用算法进行简单的问题求解和程序设计- 培养编写高效算法的能力教学内容第一章算法基础1.1 算法的定义和特性1.2 算法的分类1.3 时间复杂度和空间复杂度第二章常用算法2.1 排序算法（冒泡排序、快速排序、归并排序）2.2 查找算法（顺序查找、折半查找、哈希查找）2.3 图算法（最短路径算法、最小生成树算法）第三章算法应用3.1 算法在智能搜索、机器研究等领域的应用3.2 算法在计算机游戏、网络安全等领域的应用3.3 算法在大数据处理中的应用教学方法本课程采用讲授和实践相结合的教学方法。
教师将通过课堂讲解、板书演示、案例分析等方式向学生介绍算法基础原理和应用技巧，并通过实例编程和练巩固学生的实际应用能力。
考核方式本课程考核方式包括课堂作业、实验报告、期中考试和期末考试。
其中，期中考试占30%的成绩，期末考试占50%的成绩，课堂作业和实验报告占20%的成绩。
教材与参考书目教材《数据结构与算法分析》，作者：Mark Allen Weiss，出版社：机械工业出版社参考书目《算法导论》，作者：Thomas H. Cormen，出版社：机械工业出版社《算法设计与分析基础》，作者：Sun Limin，出版社：高等教育出版社实验环境本课程实验环境为Windows操作系统，使用Java语言进行编程实现。
教学进度。
算法设计与分析-第2章-算法分析基础PPT课件
2k
1 5(
n 2k 1
)2
L 2×5´( 2n)2
5n2
T (n)
7n
k 1 5
i0
n 2i
2
7n
5n2 (2
2
1
k 1
)
10 n2 3n 10 n2 O (n2 )
• 例: Merge-sort排序算法的复杂性递归方程为
T(n)=(1)
if n=1
T(n)=2T(n/2)+(n) if n>1
T(n) = ？
.
27
2.5 递归算法的分析
三、递推关系式的求解-- 扩展递归技术
步骤： 循环地展开递推关系式， 把递推关系式转化为求和表达式， 然后可使用求和技术解之。
能解决输入规模为多大的问题？
设在新机器上用 t 秒时间能解决输入规模为 N 的问题，则
由于此时
f (N)
N，2 新机器的运行速度/每语句为： t新
t0 , 64
代入关系式
f (N ) *t新 t ，得
N2
*
t0 64
t
n2
* t0
解，得
N 8n
思考：以上说明了什么问题？
.
14
2.2 算法的渐进分析
.
28
2.5 递归算法的分析
求以下递推式的时间复杂性
7
T (n)
2T (n
2)
5n2
解：设 n=2k
T (n) 2T (n 2) 5n2
n1 n>1
2(2T (n 4)( n 4)2 ) 5(n 2)2 ) 5n2
2k T (1)
间就一个常因子范围内而言是相同的。
算法分析基础——主定理
算法分析基础——主定理
对于形为T(n) = aT(n / b) + f(n)的递推⽅程，我们有如下结论：
主定理（MasterTheorem）设a≥1，b>1 为常数，f(n)为函数，n为⾮负整数，且 T(n) = aT(n / b) + f(n)，则有以下结果：
1. 若存在ε>0，使得f(n) = O(n log b a-ε)，则T(n) = Θ(n log b a)
2. 若f(n) = Θ(n log b a)，则T(n) = Θ(n log b a logn)
3. 若存在ε>0，使得f(n) = Ω(n log b a+ε)，并且对于某个常数c<1和所有充分⼤的n，有af(n / b)≤cf(n)，则T(n) = Θ(f(n))
证明：详见教材（推导过程略复杂，不想写了qwq）。
由主定理可以直接得到下述推论：
推论1 依主定理条件，递推⽅程为T(n)= aT(n / b) + c，则
1. 当a≠1时，T(n) = Θ(n log b a)
2. 当a=1时，T(n) = Θ(logn)
推论2 依主定理条件，递推⽅程为T(n) = aT(n / b) + cn，则
1. 当a>b时，T(n) = Θ(n log b a)
2. 当a=b时，T(n) = Θ(nlogn)
3. 当a<b时，T(n) = Θ(n)
例根据主定理及其推论，我们可以直接得到⼆分检索算法的平均时间复杂度为Θ(logn)，⽽⼆分归并排序的平均时间复杂度为Θ(nlogn)。
算法-第2章-算法效率分析基础
The Big-O and Related Notations
2.2.7 基本的效率类型
1 log n n n log n n2 n3 2n n! constant logarithmic linear n log n quadratic cubic exponential factorial
思考
2.2.2 符号О
定义1 我们把函数t(n)属于O(g(n)) ，记作t(n) ∈ O(g(n)) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界由g(n) 的常数倍数所确定，也就是说，存在大于0的常数c和非负 的整数n0，使得： 对于所有的n≥ n0来说， t(n) ≤c g(n)
cg(n)
2.2 渐进符号和基本效率类型
2.2.1 非正式的介绍
O(g(n)) 是增长次数小于等于g(n) (以及其常数倍，n趋 向于无穷大)的函数集合。 n∈O(n2),100n+5∈O(n2), n(n-1) /2 ∈O(n2),n3∈/ O(n2), Ω(g(n))，代表增长次数大于等于g(n)(以及其常数倍,n趋 向于无穷大)的函数集合。 n3∈ Ω(n2)， n(n-1) /2 ∈ Ω(n2)，但是100n+5 ∈/ Ω(n2) Θ(g(n))是增长次数等于g(n) )(以及其常数倍,n趋向于无 穷大)的函数集合。因此，每一个二次方程an2+bn+c在 a>0的情况下都包含在Θ(n2)中，除了无数类似于n2+sin n和n2+log n的函数（你能解释原因吗？）。
t(n) cg(n)
n0之前的情 况无关重要
n n0 符号Ω：t(n)∈Ω(g(n))
2.2.4 符号Θ
定义 3 我们把函数t(n)属于Θ(g(n)) ，记作t(n) ∈Θ(g(n)) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界和下 界都由g(n)的常数倍数所确定，也就是说，存在大于0的 常数c1，c2和和非负的整数n0，使得： 对于所有的n≥ n0来说， c2g(n) ≤t(n) ≤ c1g(n)
第2章 算法分析基础(《算法设计与分析(第3版)》C++版 王红梅 清华大学出版社)
3
Page 11
2.1.2 算法的渐近分析
常见的时间复杂度：
Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)
多项式时间，易解问题
算
法
指数时间，难解问题
设 计 与
分
析
（
第
时间复杂度是在不同数量级的层面上比较算法
版 ）
清
华
大
学
时间复杂度是一种估算技术（信封背面的技术）
Page 7
2.1.2 算法的渐近分析
3
每条语句执行次数之和 = 算法的执行时间 ＝ 每条语句执行时间之和
基本语句的执行次数 for (i = 1; i <= n; i++)
单位时间
算
法
设
计
与
执行次数 × 执行一次的时间
分 析 （
第
for (j = 1; j <= n; j++)
版 ）
x++;
指令系统、编译的代码质量
算法设计：面对一个问题，如何设计一个有效的算法
算
法
设
检
指
验
导
评
计 与 分 析 （ 第 版
改
估
） 清
进
华 大
学
出
版
算法分析：对已设计的算法，如何评价或判断其优劣
社
3
Page 3
2.1.1 输入规模与基本语句
如何度量算法的效率呢？
事后统计：将算法实现，测算其时间和空间开销
缺点：（1）编写程序实现算法将花费较多的时间和精力 （2）所得实验结果依赖于计算机的软硬件等环境因素
第2章 算法分析基础ppt课件
•事后测试：将算法编制成程序后放到计算机上运行，收集 其执行时间和空间占用等统计资料，进行分析 判断——直接与物理实现有关。
最新课件
7
1）事前分析
• 目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法 “好坏”。
• 如何给出反映算法执行特性的描述？
最直接方法：统计算法中各种运算的执行情况：
算法的数量级从本质上反映了一个算法的执行特性。 例：求解同一问题的三个算法分别具有n, n2 , n3数量级。 若n=10，则可能的执行时间将分别是10，100，1000 个 单位时间——与环境因素无关。
最新课件
10
• 计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）
的一个函数表示形式，一般记为与输入规模n有关 的函数形式：f(n)
则记作 f(N)=(g,(N))
含义：
• 算法在最好和最坏情况下的计算时间就一个常数因子范 围内而言是相同的。可看作：
既有f(N)=Ω(g(N))，又有f(N)=Ο(g(N))
最新课件
28
最新课件
29
算法分析方法
• 例：顺序搜索算法
template<class Type> int seqSearch(Type *a, int n, Type k) {
最新课件
13
算法的时间复杂性
• （1）最坏情况下的时间复杂性 • Tmax(n) = max{ T(I) | size(I)=n } • （2）最好情况下的时间复杂性 • Tmin(n) = min{ T(I) | size(I)=n } • （3）平均情况下的时间复杂性
• Tavg(n) =
p(I)T(I)
最新课件
7
1）事前分析
• 目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法 “好坏”。
• 如何给出反映算法执行特性的描述？
最直接方法：统计算法中各种运算的执行情况：
算法的数量级从本质上反映了一个算法的执行特性。 例：求解同一问题的三个算法分别具有n, n2 , n3数量级。 若n=10，则可能的执行时间将分别是10，100，1000 个 单位时间——与环境因素无关。
最新课件
10
• 计算时间/频率计数的表示函数 通过事前分析给出算法计算时间（频率计数）
的一个函数表示形式，一般记为与输入规模n有关 的函数形式：f(n)
则记作 f(N)=(g,(N))
含义：
• 算法在最好和最坏情况下的计算时间就一个常数因子范 围内而言是相同的。可看作：
既有f(N)=Ω(g(N))，又有f(N)=Ο(g(N))
最新课件
28
最新课件
29
算法分析方法
• 例：顺序搜索算法
template<class Type> int seqSearch(Type *a, int n, Type k) {
最新课件
13
算法的时间复杂性
• （1）最坏情况下的时间复杂性 • Tmax(n) = max{ T(I) | size(I)=n } • （2）最好情况下的时间复杂性 • Tmin(n) = min{ T(I) | size(I)=n } • （3）平均情况下的时间复杂性
• Tavg(n) =
p(I)T(I)
算法分析知识点总结
算法分析知识点总结一、算法的基本概念1.1 算法的定义：算法是一个有限指令序列，用于解决特定问题或执行特定任务的描述。
1.2 算法的特性：有穷性、确定性、可行性、输入输出和有效性。
1.3 算法的表示：伪代码和流程图是常见的算法表示方式。
1.4 算法的复杂度：算法的时间复杂度和空间复杂度是衡量算法性能的重要指标。
二、算法分析的基本方法2.1 时间复杂度：描述算法所需的运行时间与输入规模之间的关系。
2.2 空间复杂度：描述算法所需的内存空间与输入规模之间的关系。
2.3 最好情况、平均情况和最坏情况：算法复杂度分析通常考虑这三种情况的复杂度。
2.4 渐进复杂度分析：通过增长数量级的方式描述算法的复杂度。
2.5 复杂度函数的求解：基于递推关系和分析法求解算法的复杂度函数。
三、常见的时间复杂度分析方法3.1 常数阶O(1)：所有输入规模下，算法的运行时间是固定的。
3.2 线性阶O(n)：算法的运行时间与输入规模成线性关系。
3.3 对数阶O(log n)：算法的运行时间与输入规模的对数成关系。
3.4 平方阶O(n^2)及以上阶：算法的运行时间与输入规模呈指数或多项式关系。
3.5 指数阶O(2^n)：算法的运行时间与输入规模成指数关系。
四、常见的空间复杂度分析方法4.1 常数空间复杂度O(1)：算法所需的内存空间与输入规模无关。
4.2 线性空间复杂度O(n)：算法所需的内存空间与输入规模成线性关系。
4.3 对数空间复杂度O(log n)：算法所需的内存空间与输入规模的对数成关系。
4.4 平方空间复杂度O(n^2)及以上阶：算法所需的内存空间与输入规模呈指数或多项式关系。
4.5 指数空间复杂度O(2^n)：算法所需的内存空间与输入规模成指数关系。
五、常见的复杂度函数分析方法5.1 基于递推关系求解：通过递推关系式及其解的求解方法分析算法的复杂度。
5.2 基于分析法求解：通过数学分析和极限运算等方法求解算法的复杂度函数。
第2章-算法的分析基础分析解析
通过程序步来分析算法的时间复杂度
求数组元素累加之和的迭代程序： (P20 程序2-1) float Sum(float list[],const int n) { float tempsum=0.0; //1 for (int i=0;i<n;i++) //n+1 { tempsum+=list[i]; //n } return tempsum; //1 } 程序总步数为：2n+3 求数组元素累加之和的递归程序： (P21 程序2-2) float RSum(float list[],const int n) { if (n) //1 { return RSum(list,n-1)+list[n-1]; //1 } return 0; //1 }
（1）最好情况下的时间复杂性： B(n) = Tmin(n) = min{ T(n,I) | I∈Dn } （2）最坏情况下的时间复杂性： W(n) = Tmax(n) = max{ T(n,I) | I∈Dn }
（3）平均情况下的时间复杂性：
A(n) = Tavg(n) =
IDn
p(I)T(n,I)
南京邮电大学 计算机学院计科系
第2章 算法分析基础
柯昌博 日期：2015-2-6
2018/10/20
1
2.1 算法复杂度
好算法的4个重要特征： Correctness——正确性
注意区分“正确性”和“健壮性”的概念： 算法正确性——在合法的输入下，算法应实现预先规定的功能和计算精度要求。
程序健壮性——当输入不合法的数据时，程序应能做适当处理而不至于引起严重后果。
好算法的4个重要特征： Correctness——正确性 Simplicity, clarity——简明性 Amount of time/space used——效率 Optimality——最优性
第二章-算法分析基础
一具体算法的时间复杂度和空间复杂度往往是不独立的， 在算法设计中要在时间效率和空间效率之间折衷。
2.2.1 非递归算法分析
1．仅依赖于问题规模的时间复杂度
有一类简单的问题，其操作具有普遍性，也就是说对所 有的数据均等价地进行处理，这类算法的时间复杂度，很 容易分析。
【例1】交换i和j的内容。
Temp=i；i=j；j=temp；
递归
回溯
迭代法介绍：
用迭代方法估计递归算法的解, 就是充分利用递归算法中的 递归关系,通过一定的代数运算和数学分析的级数知识,得到问 题的复杂度。
递归方程具体就是利用递归算法中的递归关系写出递归方程, 迭代地展开的右端，使之成为一个非递归的和式,然后通过对和 式的估计来达到对方程左端即方程的解的估计。
例如：
for( j=1;j<=n;++j) for(k=1;k<=n;++k)
++x；
语句“++x、k<=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j<=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。
经常从算法中选取一种对于所研究的问题来说是基本(或者 说是主要) 的原操作,以该基本操作在算法中重复执行的次数作 为算法运行时间的衡量准则。这个原操作,多数情况下是最深层 次循环体内的语句中的原操作。
精品课件！
精品课件！
2．提高效率。
1）以提高算法的全局效率为主，提高局部效率为辅。 2）在优化算法的效率时，应当先找出限制效率的“瓶颈”。 3）多数情况下，时间效率和空间效率可能是对立的，此时
应当分析哪个更重要，作出适当的折衷。 4）可以考虑先选取合适的数据结构，再优化算法。 5）递归过程的实现决定了递归算法的效率往往很低，费
2.2.1 非递归算法分析
1．仅依赖于问题规模的时间复杂度
有一类简单的问题，其操作具有普遍性，也就是说对所 有的数据均等价地进行处理，这类算法的时间复杂度，很 容易分析。
【例1】交换i和j的内容。
Temp=i；i=j；j=temp；
递归
回溯
迭代法介绍：
用迭代方法估计递归算法的解, 就是充分利用递归算法中的 递归关系,通过一定的代数运算和数学分析的级数知识,得到问 题的复杂度。
递归方程具体就是利用递归算法中的递归关系写出递归方程, 迭代地展开的右端，使之成为一个非递归的和式,然后通过对和 式的估计来达到对方程左端即方程的解的估计。
例如：
for( j=1;j<=n;++j) for(k=1;k<=n;++k)
++x；
语句“++x、k<=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j<=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。
经常从算法中选取一种对于所研究的问题来说是基本(或者 说是主要) 的原操作,以该基本操作在算法中重复执行的次数作 为算法运行时间的衡量准则。这个原操作,多数情况下是最深层 次循环体内的语句中的原操作。
精品课件！
精品课件！
2．提高效率。
1）以提高算法的全局效率为主，提高局部效率为辅。 2）在优化算法的效率时，应当先找出限制效率的“瓶颈”。 3）多数情况下，时间效率和空间效率可能是对立的，此时
应当分析哪个更重要，作出适当的折衷。 4）可以考虑先选取合适的数据结构，再优化算法。 5）递归过程的实现决定了递归算法的效率往往很低，费
第2章 算法效率分析基础
❖输入规模的度量：（问题规模）
一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行 更长的时间（即算法耗费的时间随着输入规模的增大而增加） 。例如： 1. 更大的数组排序需要花费更多的运行时间； 2. 更大的矩阵相乘需要花费更多的运算时间。 因此，采用一个以算法输入规模 n 为参数的函数，来研究算法效率就是 非常合乎逻辑的。 输入规模的选择问题： 在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、 查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度； 对于 n 次多项式求值问题，这个参数是多项式次数或者系数个数。 4
5
❖运行时间的度量：
接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位 （秒、毫秒等）来度量算法的运行时间呢？其理由如下： 1. 它依赖于特定计算机的运行速度； 2. 它依赖于实现算法的代码质量；（程序员编程的水平问题） 3. 它依赖于编译器的好坏；（编译成机器码的质量，即指令条数） 4. 它还依赖于一些其他问题如操作系统的调度策略等。 鉴于此，希望找到一个不依赖于上述因素的时间度量。 问：是否统计算法的每步操作执行次数来作为算法的时间效率度量呢？ 答：无此必要且较困难。一个算法中有许多操作，决定算法时间效率的 是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法 时间效率，这些最关键的操作步称为基本操作，它们对算法执行时间的 占用最大（基本操作即算法中最费时的操作）。所以，用基本操作执行 次数来作为时间效率的度量。
前述已知，我们用输入规模 n 的函数 T(n) 来度量算法的效率。若T(n) 随 n 增长快，则算法效率较差；若T(n) 随 n 增长较慢，则算法效率更好。 这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模 有关，且与特定的输入有关。下面以顺序查找算法为例：
一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行 更长的时间（即算法耗费的时间随着输入规模的增大而增加） 。例如： 1. 更大的数组排序需要花费更多的运行时间； 2. 更大的矩阵相乘需要花费更多的运算时间。 因此，采用一个以算法输入规模 n 为参数的函数，来研究算法效率就是 非常合乎逻辑的。 输入规模的选择问题： 在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、 查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度； 对于 n 次多项式求值问题，这个参数是多项式次数或者系数个数。 4
5
❖运行时间的度量：
接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位 （秒、毫秒等）来度量算法的运行时间呢？其理由如下： 1. 它依赖于特定计算机的运行速度； 2. 它依赖于实现算法的代码质量；（程序员编程的水平问题） 3. 它依赖于编译器的好坏；（编译成机器码的质量，即指令条数） 4. 它还依赖于一些其他问题如操作系统的调度策略等。 鉴于此，希望找到一个不依赖于上述因素的时间度量。 问：是否统计算法的每步操作执行次数来作为算法的时间效率度量呢？ 答：无此必要且较困难。一个算法中有许多操作，决定算法时间效率的 是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法 时间效率，这些最关键的操作步称为基本操作，它们对算法执行时间的 占用最大（基本操作即算法中最费时的操作）。所以，用基本操作执行 次数来作为时间效率的度量。
前述已知，我们用输入规模 n 的函数 T(n) 来度量算法的效率。若T(n) 随 n 增长快，则算法效率较差；若T(n) 随 n 增长较慢，则算法效率更好。 这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模 有关，且与特定的输入有关。下面以顺序查找算法为例：
算法-第2章-算法效率分析基础(李静)
2.2.2 符号О
定义1 我们把函数t(n)属于O(g(n)) ，记作t(n) ∈ O(g(n)) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界由g(n) 的常数倍数所确定，也就是说，存在大于0的常数c和非负 的整数n0，使得： 对于所有的n≥ n0来说， t(n) ≤c g(n)
cg(n)
思考
• • • • P46 2T P46 4.bT P46 5T P46 6.aT
补充知识
• 渐近分析中函数比较
– 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.
• 无论是最差效率分析还是最优效率分析都不能提供一 种必要的信息：在“典型”或者“随机”输入的情况 下， 一个算法会具有什么样的行为。这正是平均效率 试图提供给我们信息。 • 摊销效率: 它并不适用于算法的单次运行，而是应用于 算法对同样数据结构所执行的一系列操作。
2.1.4 算法的最优、最差和平均效率
对于两个连续执行部分组成的算法，应该如何应 用这个特性呢？它意味着该算法的整体效率是由 具有较大的增长次数的部分所决定的，即它的效 率较差的部分.
பைடு நூலகம்
算法分析：加法规则
t(n, m)=t1(n)+t2 (m) ∈O(max (f (n), g (m)))
两个并列循环的例子 void example (float x[ ][ ], int m, int n, int k) { float sum [ ]; for ( int i=0; i<m; i++ ) { //x[][]中各行 sum[i] = 0.0; //数据累加 for ( int j=0; j<n; j++ ) sum[i]+=x[i][j]; } for ( i = 0; i < m; i++ ) //打印各行数据和 cout << “Line ” << i << “ : ” <<sum [i] << endl; } 渐进时间复杂度为O(max (m*n, m))
第2章 算法分析基础
2
n
3. 通用分治递推式
大小为n的原问题分成若干个大小为n/b的子问题， 其中a个子问题需要求解，而cnk是合并各个子问题 的解需要的工作量。
c T ( n) = k + aT ( n b ) cn n =1
n>1
k > a b k = a b k < a b
22
O ( nlog b a ) k = T ( n) O ( n log b n) k O ( n )
2014-3-9 算法设计与分析--绪论 19
2.1.5 递归算法的时间复杂性分析
关键：根据递归过程建立递推关系式，然 后求解这个递推关系式。 1. 猜测技术:对递推关系式估计一个上限， 然后（用数学归纳法）证明它正确。 当只求解算法的近似复杂性时，猜测技术是 一种很有用的技术。
2014-3-9 算法设计与分析--绪论 20
执 行 次 数
T(n) c×g(n)
n0 之 前 的 情况无关 紧要 n0
2014-3-9 算法设计与分析--绪论
问题规模n
8
说明
大Ω符号用于描述增长率的下限，这个下限 的阶越高，结果就越有价值。
举例：矩阵乘法问题的时间下界为 Ω(n2)
基于比较的排序算法的时间下界为 Ω(nlogn)
2014-3-9
2014-3-9
算法设计与分析--绪论
3
2.1.1 输入规模与基本语句
时间复杂性分析的关键：
问题规模：输入量的多少；
基本语句：执行次数与整个算法的执行时间
成正比的语句
2014-3-9
算法设计与分析--绪论
4
例2.1 对顺序查找算法，找出输入规模 和基本语句 例2.2 对冒泡排序算法，找出输入规模和 基本语句
n
3. 通用分治递推式
大小为n的原问题分成若干个大小为n/b的子问题， 其中a个子问题需要求解，而cnk是合并各个子问题 的解需要的工作量。
c T ( n) = k + aT ( n b ) cn n =1
n>1
k > a b k = a b k < a b
22
O ( nlog b a ) k = T ( n) O ( n log b n) k O ( n )
2014-3-9 算法设计与分析--绪论 19
2.1.5 递归算法的时间复杂性分析
关键：根据递归过程建立递推关系式，然 后求解这个递推关系式。 1. 猜测技术:对递推关系式估计一个上限， 然后（用数学归纳法）证明它正确。 当只求解算法的近似复杂性时，猜测技术是 一种很有用的技术。
2014-3-9 算法设计与分析--绪论 20
执 行 次 数
T(n) c×g(n)
n0 之 前 的 情况无关 紧要 n0
2014-3-9 算法设计与分析--绪论
问题规模n
8
说明
大Ω符号用于描述增长率的下限，这个下限 的阶越高，结果就越有价值。
举例：矩阵乘法问题的时间下界为 Ω(n2)
基于比较的排序算法的时间下界为 Ω(nlogn)
2014-3-9
2014-3-9
算法设计与分析--绪论
3
2.1.1 输入规模与基本语句
时间复杂性分析的关键：
问题规模：输入量的多少；
基本语句：执行次数与整个算法的执行时间
成正比的语句
2014-3-9
算法设计与分析--绪论
4
例2.1 对顺序查找算法，找出输入规模 和基本语句 例2.2 对冒泡排序算法，找出输入规模和 基本语句
Algorithm 2
3
Analysis and Design of Computer Algorithms
分析框架——输入规模度量
输入规模度量
算法的时间效率和空间效率都用输入规模的函 数进行度量。 对于所有的算法，对于规模更大的输入都需要 运行更长的时间。 经常使用一个输入规模n为参数的函数来研究 算法的效率。 选择输入规模的合适量度，要受到所讨论算法 的操作细节影响。
斐波那契数列
0,1,1,2,3,5,8,13,21,34,……
F(n)= F(n-1)+F(n-2) , n>1 1 , n=1 0 ,n=0
21
Analysis and Design of Computer Algorithms
算法的经验分析
对算法效率做经验分析的通用方案
了解试验的目的 决定用来度量效率的量度M和度量单位（单位时 间内的操作次数） 决定输入样本的特性 为实验准备算法的程序实现 生成输入样本 对输入样本进行计算，并记录观察到的实验数据 分析获得的实验数据
不是所有能计算的都有价值，不是所有有价值的都能被计算
——阿尔伯特.爱因斯坦 2
Analysis and Design of Computer Algorithms
教学内容
算法效率分析框架 算法效率的表示符号 非递归算法的效率分析 递归算法的效率分析 算法的经验分析 要求
掌握算法中近似时间的表示、非递归、递归算法 的效率分析方法，了解算法的经验分析
24
Analysis and Design of Computer Algorithms
静态算法可视法
25
Analysis and Design of Computer Algorithms
Analysis and Design of Computer Algorithms
分析框架——输入规模度量
输入规模度量
算法的时间效率和空间效率都用输入规模的函 数进行度量。 对于所有的算法，对于规模更大的输入都需要 运行更长的时间。 经常使用一个输入规模n为参数的函数来研究 算法的效率。 选择输入规模的合适量度，要受到所讨论算法 的操作细节影响。
斐波那契数列
0,1,1,2,3,5,8,13,21,34,……
F(n)= F(n-1)+F(n-2) , n>1 1 , n=1 0 ,n=0
21
Analysis and Design of Computer Algorithms
算法的经验分析
对算法效率做经验分析的通用方案
了解试验的目的 决定用来度量效率的量度M和度量单位（单位时 间内的操作次数） 决定输入样本的特性 为实验准备算法的程序实现 生成输入样本 对输入样本进行计算，并记录观察到的实验数据 分析获得的实验数据
不是所有能计算的都有价值，不是所有有价值的都能被计算
——阿尔伯特.爱因斯坦 2
Analysis and Design of Computer Algorithms
教学内容
算法效率分析框架 算法效率的表示符号 非递归算法的效率分析 递归算法的效率分析 算法的经验分析 要求
掌握算法中近似时间的表示、非递归、递归算法 的效率分析方法，了解算法的经验分析
24
Analysis and Design of Computer Algorithms
静态算法可视法
25
Analysis and Design of Computer Algorithms
第二章 算法分析基础
2
3
m
n
定理2.1:
若 A(n)=amnm+…+a1n+a0 是关于n的m次 多项式，则 A(n)= (nm)
算法分成两类：多项式阶算法和指数阶算 法。
O (1) O (log 2 log 2 n ) O (log 2 n ) O ( n ) O ( n log 2 n ) O ( n ) O ( n ) O ( 2 )
证明一系列语句确实做了符合规定的操作。
“正确”的含义分为以下四个层次：
①算法不含语法错误 ②算法对于几组输入数据能够得出满足 规格说明要求的结果 ③算法对于精心选择的典型、苛刻而带 有刁难性的几组数据能够得出满足规格 说明要求的结果 ④算法对一切合法的输入数据都能产生 满足规格说明要求的结果
Testing (测试)
Black
2．时间复杂性
度量时间复杂性的标准： （1）能告诉算法所采用的方法的时间效率； （2）与算法描述语言及设计风格无关； （3）与算法的许多细节无关； （4）足够精确和具有一般性。 基本运算（关键操作） 对所研究问题的基本操作 时间复杂性
一个算法的时间复杂性是指该算法的基本运算次数 算法的时间复杂性还与输入数据元素的个数（输入规 模，输入的大小）和输入数据的状态有关
评估算法的5条准则： 1 正确性 2 时间复杂性 3 占用空间(指令、数据和环境栈空间) 4 可读性 5 坚固性(健壮性)
1．正确性
一个算法包括两方面内容：一是解决问 题的方法，二是实现这一方法的一系列指 令（语句、步骤）。
确认一个算法所用方法和（或）所用公式
的正确性，可能需要相关的引理和定理。
例2.1 A是一个含有n个不同元素的实数数 组，给出求A之最大和最小元素的算法。
3
m
n
定理2.1:
若 A(n)=amnm+…+a1n+a0 是关于n的m次 多项式，则 A(n)= (nm)
算法分成两类：多项式阶算法和指数阶算 法。
O (1) O (log 2 log 2 n ) O (log 2 n ) O ( n ) O ( n log 2 n ) O ( n ) O ( n ) O ( 2 )
证明一系列语句确实做了符合规定的操作。
“正确”的含义分为以下四个层次：
①算法不含语法错误 ②算法对于几组输入数据能够得出满足 规格说明要求的结果 ③算法对于精心选择的典型、苛刻而带 有刁难性的几组数据能够得出满足规格 说明要求的结果 ④算法对一切合法的输入数据都能产生 满足规格说明要求的结果
Testing (测试)
Black
2．时间复杂性
度量时间复杂性的标准： （1）能告诉算法所采用的方法的时间效率； （2）与算法描述语言及设计风格无关； （3）与算法的许多细节无关； （4）足够精确和具有一般性。 基本运算（关键操作） 对所研究问题的基本操作 时间复杂性
一个算法的时间复杂性是指该算法的基本运算次数 算法的时间复杂性还与输入数据元素的个数（输入规 模，输入的大小）和输入数据的状态有关
评估算法的5条准则： 1 正确性 2 时间复杂性 3 占用空间(指令、数据和环境栈空间) 4 可读性 5 坚固性(健壮性)
1．正确性
一个算法包括两方面内容：一是解决问 题的方法，二是实现这一方法的一系列指 令（语句、步骤）。
确认一个算法所用方法和（或）所用公式
的正确性，可能需要相关的引理和定理。
例2.1 A是一个含有n个不同元素的实数数 组，给出求A之最大和最小元素的算法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
其中评价算法的三条主要标准是：
(1) 算法实现所耗费的时间； (2) 算法实现所所耗费的存储空间，其中
主要考虑辅助存储空间； (3) 算法应易于理解，易于编码，易于调
试等等。
2.1.2 算法的时间复杂性
1.和算法执行时间相关的因素：
1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略 4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度
上节
下节
【例1】求n!
递归方程为： T(n)=T(n-1)+O(1) 其中O(1)为一次乘法操作.
迭代求解过程如下：
T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) …… =O(1)+……+O(1)+O(1)+O(1) =n*O(1) =O(n)
【例2】抽象地考虑以下复杂一点的递归方程，且假设
最有实际价值的,是最坏情况下的时间复杂性。
2.1.3 算法的空间复杂性
算法的存储量包括：
1) 输入数据所占空间:取决于问题本身,与算法无关 2) 算法本身所占空间:相对固定 3) 辅助变量所占空间
研究算法的空间效率， 只需要分析除输入和算法之 外的额外空间。 若所需额外空间相对于输入数据量来 说是常数，则称此算法为原地工作, 否则,它应当是规模 的一个函数。
一具体算法的时间复杂度和空间复杂度往往是不独立的， 在算法设计中要在时间效率和空间效率之间折衷。
2.2.1 非递归算法分析
1．仅依赖于问题规模的时间复杂度
有一类简单的问题，其操作具有普遍性，也就是说对所 有的数据均等价地进行处理，这类算法的时间复杂度，很 容易分析。
【例1】交换i和j的内容。
Temp=i；i=j；j=temp；
NP问题:至今没有找到多项式时间算法解的一类问题,可以 在多项式时间内验证一个解是否正确的问题,亦称为易验 证问题类。
NP完全问题(NPC问题,C代表complete):从NP类的问题 中分出复杂性最高的一个子类。
•如果一个NPC问题存在多项式时间的算法，则所有的NP 问题都可以在多项式时间内求解，即P=NP成立!! •要么每个NP完全问题都存在多项式时间的算法（即通常 所指的有效算法）；要么所有NP完全问题都不存在多项 式时间的算法。
数量级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C，使
则称f(n)与g(n)是同数量级的函数。
算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式 (n为问题的规模,c为一常量)：
Ο(1)称为常数级 Ο(logn)称为对数级 Ο(n)称为线性级 Ο(nc)称为多项式级
若对于查找不同元素的概率P不相同时，其算法复杂 度就只能做近似分析，或在构造更好的算法或存储结构后， 做较准确的分析。
上节
下节
2.2.2 递归算法分析
【例1】求N！
构造算法中的两个步骤：
1）N!=N*(N-1)！
2）0!=1， 1!=1。
递归算法如下：
以n=3为例,调用过程如下：
fact(3)-fact(2)-fact(1)-fact(2)-fact(3)
y++
上节
下节
【例3】循环次数间接依赖规模n
(1) x=1； (2) for(i=1；i<=n；i++) (3) for( j=1；j<=i；j++) (4) for(k=1；k<=j；k++) (5) x++； 该算法段中频度最大的语句是(5)，从内层循环向外层分析 语句(5)的执行次数：
则该算法段的时间复杂度为：T(n)=O(n3 /6+低次项)= O(n3)。
2．提高效率。
1）以提高算法的全局效率为主，提高局部效率为辅。 2）在优化算法的效率时，应当先找出限制效率的“瓶颈”。 3）多数情况下，时间效率和空间效率可能是对立的，此时
应当分析哪个更重要，作出适当的折衷。 4）可以考虑先选取合适的数据结构，再优化算法。 5）递归过程的实现决定了递归算法的效率往往很低，费
以上三条单个语句的频度均为1，该算法段的执行时间 是一个与问题规模n无关的常数。算法的时间复杂度为常 数阶，记作T(n)=Ο(1)。
如果算法的执行时间不随着问题规模n的增加而增长， 即使算法中有上千条语句,其执行时间也不过是一个较大的 常数。此类算法的时间复杂度是Ο(1)。
上节
下节
【例2】循环次数直接依赖规模n
2.算法的时间复杂度还与输入实例的初始状态有关。
这类算法的时间复杂度的分析比较复杂，一般分最好情 况（处理最少的情况),最坏情况(处理最多的情况)和平均情 况分别进行讨论。
【例4】
【例4】在数值A[0..n-1]中查找给定值K的算法大 致如下：
(1) i=n-1； (2) while( i>=0 and A[i]<>k ) (3) i=i-1； (4) return i；
Ο(cn)称此为指数级
Ο(n!)称为阶乘级
以上时间复杂度级别是由低到高排列的,其随规模n的增长 率，由图2-1可见一斑：
图2-1 T(n)与规模n的函数关系
原则上一个算法的时间复杂度, 最好不要采用指数级和阶 乘级的算法, 而应尽可能选用多项式级或线性级等时间复 杂度级别较小的算法。
对于较复杂的算法，可将它分隔成容易估算的几个部分， 然后再利用“O"的求和原则得到整个算法的时间复杂度。
度量标准：
一.计算所需的步数或指令条数(这叫时间复杂度)。 二.计算所需的存储单元数量(这叫空间复杂度)。
上节
下节
问题的复杂性和算法的复杂性的区别： 只就时间复杂性说，算法的复杂性是指解决问题
的一个具体的算法的执行时间，这是算法的性质； 问题的复杂性是指这个问题本身的复杂程度。
P类问题:就是所有复杂度为多项式时间的问题的集 合(易解的问题类,否则为难解的问题)。 例如:梵塔问题 推销员旅行问题等
第二章 算法分析基础
2.1 算法分析体系及计量
算法分析的任务: 对设计出的每一个具体的算法,利用数
学工具，讨论其复杂度。
2.1.1 算法分析的评价体系
对算法的评价有两个大的方面：
一.对算法的维护的方便性。
二.算法在实现运行时占有的机器资源 的多少,即算法的运行的时间和空间效率。
对算法的分析和评价，一般应考虑正确性、可 维护性、可读性、运算量及占用存储空间等诸多 因素。
时和费内存空间。在解决问题时，如果能使用递推法 解决的，应考虑用递推法，其效率更高些。 6）注意多用数学方法，可以大大提高算法效率。 7）另外还有一些细节上的问题,如:乘、除运算的效率比 加、减法运算低。
例：若算法的两个部分的时间复杂度分别为 T1(n)=O(f(n)) 和 T2(n)=O(g(n))，
则总的时间复杂度为： T(n)=T1(n)+．问题时间复杂度的上界和下界
略
5.算法时间复杂度的最好情况和最坏情况
我们要确定能反映出算法在各种情况下工作的数据集, 选取的数据要能够反映、代表各种计算情况下的估算, 包 括 最好情况下的时间复杂度(Tmax) 最坏情况下的时间复杂度(Tmin) 平均情况下的时间复杂度(Tavg)
前，一定要有确切的含义，或是被赋值或是经模块接口 传递信息。 3）算法中要当心变量发生上溢或下溢，数组的下标越界。 4）写算法时就要考虑，可能出现错误的情况，提示执行错 误处理算法。 5）编写算法时区别问题的循环条件和停止条件，不要误用。 6）注意算法中循环体，或条件体的内容，不要误把循环体 内的操作写互循环体外或者出现相反的错误。
算法的空间复杂度是指算法在执行过程中所占辅助 存储空间的大小用S(n)表示。 算法的空间复杂度S(n)也可表示为:
S(n)=Ο(g(n)) 表示随着问题规模n的增大, 算法运行所需存储量的增 长率与g(n)的增长率相同。
2.1.4 NP完全问题
NP完全性问题:属于“计算复杂性”研究的课题。 计算复杂性:就是用计算机求解问题的难易程度。
3．时间复杂度估算
因为： 算法=控制结构+原操作(固有数据类型的操作)
所以：
算法的执行时间= 原 操作的执行次数*原操作的执行时间
语句的频度指的是该语句重复执行的次数。
一个算法转换为算法后所耗费的时间,除了与所用的计算软、 硬件环境有关外，主要取决于算法中指令重复执行的次数，即语 句的频度相关。
一个算法中所有语句的频度之和构成了该算法的 运行时间。
此算法的频度不仅与问题规模n有关，还与输入实 例中A的各元素取值及k的取值有关：
1. 若A中没有与k相等的元素，则语句(2)的频度 f(n)=n；这是最坏情况。
2. 若A的最后一个元素等于k,则语句(2)的频度f(n) 是常数1;这是最好情况。
在求平均情况时，一般地假设查找不同元素的概率P是 相同的,则算法的平均复杂度为：
例如：
for( j=1;j<=n;++j) for(k=1;k<=n;++k)
++x；
语句“++x、k<=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j<=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。
经常从算法中选取一种对于所研究的问题来说是基本(或者 说是主要) 的原操作,以该基本操作在算法中重复执行的次数作 为算法运行时间的衡量准则。这个原操作,多数情况下是最深层 次循环体内的语句中的原操作。
(1) x=0；=0； (2) for(k-1；<=n；++) (3) x++； (4) for(i=1；<=n；++) (5) for( j=1；j<=n；++) (6) y++；
(1) 算法实现所耗费的时间； (2) 算法实现所所耗费的存储空间，其中
主要考虑辅助存储空间； (3) 算法应易于理解，易于编码，易于调
试等等。
2.1.2 算法的时间复杂性
1.和算法执行时间相关的因素：
1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略 4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度
上节
下节
【例1】求n!
递归方程为： T(n)=T(n-1)+O(1) 其中O(1)为一次乘法操作.
迭代求解过程如下：
T(n)=T(n-2)+O(1)+O(1) =T(n-3)+O(1)+O(1)+O(1) …… =O(1)+……+O(1)+O(1)+O(1) =n*O(1) =O(n)
【例2】抽象地考虑以下复杂一点的递归方程，且假设
最有实际价值的,是最坏情况下的时间复杂性。
2.1.3 算法的空间复杂性
算法的存储量包括：
1) 输入数据所占空间:取决于问题本身,与算法无关 2) 算法本身所占空间:相对固定 3) 辅助变量所占空间
研究算法的空间效率， 只需要分析除输入和算法之 外的额外空间。 若所需额外空间相对于输入数据量来 说是常数，则称此算法为原地工作, 否则,它应当是规模 的一个函数。
一具体算法的时间复杂度和空间复杂度往往是不独立的， 在算法设计中要在时间效率和空间效率之间折衷。
2.2.1 非递归算法分析
1．仅依赖于问题规模的时间复杂度
有一类简单的问题，其操作具有普遍性，也就是说对所 有的数据均等价地进行处理，这类算法的时间复杂度，很 容易分析。
【例1】交换i和j的内容。
Temp=i；i=j；j=temp；
NP问题:至今没有找到多项式时间算法解的一类问题,可以 在多项式时间内验证一个解是否正确的问题,亦称为易验 证问题类。
NP完全问题(NPC问题,C代表complete):从NP类的问题 中分出复杂性最高的一个子类。
•如果一个NPC问题存在多项式时间的算法，则所有的NP 问题都可以在多项式时间内求解，即P=NP成立!! •要么每个NP完全问题都存在多项式时间的算法（即通常 所指的有效算法）；要么所有NP完全问题都不存在多项 式时间的算法。
数量级相等是这样定义的,设f(n)是一个关于正整数n 的函数,若存在一个常数C，使
则称f(n)与g(n)是同数量级的函数。
算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式 (n为问题的规模,c为一常量)：
Ο(1)称为常数级 Ο(logn)称为对数级 Ο(n)称为线性级 Ο(nc)称为多项式级
若对于查找不同元素的概率P不相同时，其算法复杂 度就只能做近似分析，或在构造更好的算法或存储结构后， 做较准确的分析。
上节
下节
2.2.2 递归算法分析
【例1】求N！
构造算法中的两个步骤：
1）N!=N*(N-1)！
2）0!=1， 1!=1。
递归算法如下：
以n=3为例,调用过程如下：
fact(3)-fact(2)-fact(1)-fact(2)-fact(3)
y++
上节
下节
【例3】循环次数间接依赖规模n
(1) x=1； (2) for(i=1；i<=n；i++) (3) for( j=1；j<=i；j++) (4) for(k=1；k<=j；k++) (5) x++； 该算法段中频度最大的语句是(5)，从内层循环向外层分析 语句(5)的执行次数：
则该算法段的时间复杂度为：T(n)=O(n3 /6+低次项)= O(n3)。
2．提高效率。
1）以提高算法的全局效率为主，提高局部效率为辅。 2）在优化算法的效率时，应当先找出限制效率的“瓶颈”。 3）多数情况下，时间效率和空间效率可能是对立的，此时
应当分析哪个更重要，作出适当的折衷。 4）可以考虑先选取合适的数据结构，再优化算法。 5）递归过程的实现决定了递归算法的效率往往很低，费
以上三条单个语句的频度均为1，该算法段的执行时间 是一个与问题规模n无关的常数。算法的时间复杂度为常 数阶，记作T(n)=Ο(1)。
如果算法的执行时间不随着问题规模n的增加而增长， 即使算法中有上千条语句,其执行时间也不过是一个较大的 常数。此类算法的时间复杂度是Ο(1)。
上节
下节
【例2】循环次数直接依赖规模n
2.算法的时间复杂度还与输入实例的初始状态有关。
这类算法的时间复杂度的分析比较复杂，一般分最好情 况（处理最少的情况),最坏情况(处理最多的情况)和平均情 况分别进行讨论。
【例4】
【例4】在数值A[0..n-1]中查找给定值K的算法大 致如下：
(1) i=n-1； (2) while( i>=0 and A[i]<>k ) (3) i=i-1； (4) return i；
Ο(cn)称此为指数级
Ο(n!)称为阶乘级
以上时间复杂度级别是由低到高排列的,其随规模n的增长 率，由图2-1可见一斑：
图2-1 T(n)与规模n的函数关系
原则上一个算法的时间复杂度, 最好不要采用指数级和阶 乘级的算法, 而应尽可能选用多项式级或线性级等时间复 杂度级别较小的算法。
对于较复杂的算法，可将它分隔成容易估算的几个部分， 然后再利用“O"的求和原则得到整个算法的时间复杂度。
度量标准：
一.计算所需的步数或指令条数(这叫时间复杂度)。 二.计算所需的存储单元数量(这叫空间复杂度)。
上节
下节
问题的复杂性和算法的复杂性的区别： 只就时间复杂性说，算法的复杂性是指解决问题
的一个具体的算法的执行时间，这是算法的性质； 问题的复杂性是指这个问题本身的复杂程度。
P类问题:就是所有复杂度为多项式时间的问题的集 合(易解的问题类,否则为难解的问题)。 例如:梵塔问题 推销员旅行问题等
第二章 算法分析基础
2.1 算法分析体系及计量
算法分析的任务: 对设计出的每一个具体的算法,利用数
学工具，讨论其复杂度。
2.1.1 算法分析的评价体系
对算法的评价有两个大的方面：
一.对算法的维护的方便性。
二.算法在实现运行时占有的机器资源 的多少,即算法的运行的时间和空间效率。
对算法的分析和评价，一般应考虑正确性、可 维护性、可读性、运算量及占用存储空间等诸多 因素。
时和费内存空间。在解决问题时，如果能使用递推法 解决的，应考虑用递推法，其效率更高些。 6）注意多用数学方法，可以大大提高算法效率。 7）另外还有一些细节上的问题,如:乘、除运算的效率比 加、减法运算低。
例：若算法的两个部分的时间复杂度分别为 T1(n)=O(f(n)) 和 T2(n)=O(g(n))，
则总的时间复杂度为： T(n)=T1(n)+．问题时间复杂度的上界和下界
略
5.算法时间复杂度的最好情况和最坏情况
我们要确定能反映出算法在各种情况下工作的数据集, 选取的数据要能够反映、代表各种计算情况下的估算, 包 括 最好情况下的时间复杂度(Tmax) 最坏情况下的时间复杂度(Tmin) 平均情况下的时间复杂度(Tavg)
前，一定要有确切的含义，或是被赋值或是经模块接口 传递信息。 3）算法中要当心变量发生上溢或下溢，数组的下标越界。 4）写算法时就要考虑，可能出现错误的情况，提示执行错 误处理算法。 5）编写算法时区别问题的循环条件和停止条件，不要误用。 6）注意算法中循环体，或条件体的内容，不要误把循环体 内的操作写互循环体外或者出现相反的错误。
算法的空间复杂度是指算法在执行过程中所占辅助 存储空间的大小用S(n)表示。 算法的空间复杂度S(n)也可表示为:
S(n)=Ο(g(n)) 表示随着问题规模n的增大, 算法运行所需存储量的增 长率与g(n)的增长率相同。
2.1.4 NP完全问题
NP完全性问题:属于“计算复杂性”研究的课题。 计算复杂性:就是用计算机求解问题的难易程度。
3．时间复杂度估算
因为： 算法=控制结构+原操作(固有数据类型的操作)
所以：
算法的执行时间= 原 操作的执行次数*原操作的执行时间
语句的频度指的是该语句重复执行的次数。
一个算法转换为算法后所耗费的时间,除了与所用的计算软、 硬件环境有关外，主要取决于算法中指令重复执行的次数，即语 句的频度相关。
一个算法中所有语句的频度之和构成了该算法的 运行时间。
此算法的频度不仅与问题规模n有关，还与输入实 例中A的各元素取值及k的取值有关：
1. 若A中没有与k相等的元素，则语句(2)的频度 f(n)=n；这是最坏情况。
2. 若A的最后一个元素等于k,则语句(2)的频度f(n) 是常数1;这是最好情况。
在求平均情况时，一般地假设查找不同元素的概率P是 相同的,则算法的平均复杂度为：
例如：
for( j=1;j<=n;++j) for(k=1;k<=n;++k)
++x；
语句“++x、k<=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j<=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。
经常从算法中选取一种对于所研究的问题来说是基本(或者 说是主要) 的原操作,以该基本操作在算法中重复执行的次数作 为算法运行时间的衡量准则。这个原操作,多数情况下是最深层 次循环体内的语句中的原操作。
(1) x=0；=0； (2) for(k-1；<=n；++) (3) x++； (4) for(i=1；<=n；++) (5) for( j=1；j<=n；++) (6) y++；