10
4. 我们的主要任务
算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明（程序的形式化证明技术） 4）分析算法：算法时空特性分析 5）测试程序：“调试只能指出有错误，而不能指出它
们 不存在错误”
本课程集中于学习算法的设计与分析。通过学习，掌握 计算机算法设计和分析基本策略与方法，为设计更复杂、更 有效的算法奠定基础。
·字符串操作：与字符串中字符的数量成正比 ·记录操作：与记录的属性数、属性类型等有关 · 特点：运算时间无定量
如何分析非时间囿界于常数的运算：分解成若 干时间囿界于常数的运算。
如：Tstring = Length（String）* tchar
16
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工 作的数据配置。然后使用这些数据配置运行算法， 以了解算法的性能。
进行算法分析的基本技术：抽象
13
2. 重要的假设和约定
1）计算机模型的假设
Turing机模型：计算机形式理论模型
通用计算机模型：
➢
顺序计算机
➢
有足够的“内存”
➢
能在固定的时间内存取数据单元
14
2）计算的约定 算法的执行时间=∑Fi*ti
该运算其执中行，一Fi次是所算用法的中时用间到。的某种运算i的次数， ti是
测试数据集的生成在目前算法证明与程序正确性 证明没有取得理论上的突破性进展的情况下，是 程序测试与算法分析中的关键技术之一。 ·作为算法分析的数据集：典型特征 ·作为程序性能测试的数据集：对执行指标产生 影响的性质
17
3. 如何进行算法分析？
对算法进行全面分析，可分两个阶段进行：
事前分析：就算法本身，通过对其执行性能的理论分析， 得出关于算法特性——时间和空间的一个特征 函数（Ο、Ω）——与计算机物理软硬件没有 直接关系。
6
2.算法的五个重要特性
确定性、能行性、输入、输出、有穷性
1）确定性：算法的每种运算必须要有确切的定 义，不能有二义性。
例：不符合确定性的运算
5/0
将6或7与x相加
未赋值变量参与运算
7
2ห้องสมุดไป่ตู้能行性 算法中有待实现的运算都是基本的运算，
原理上每种运算都能由人用纸和笔在有限的时间 内完成。 例：整数的算术运算是“能行”的
执行某种任务的过程 数据结构（data structure）是一种系统组织
和访问数据的方法 算法：计算机软件的灵魂
3
问题求解(Problem Solving)
理解问题
精确解或近似解 选择数据结构 算法设计策略
设计算法
证明正确性
分析算法
设计程序
4
章节安排
第一章 导引与基本数据结构
√
第二章 分治法
11
5. 课程关系
数据结构 程序设计语言：结构化设计 数学基础 非数值计算领域的基本知识
12
1.2 分析算法
1. 分析算法的目的 在于：通过对算法的分析，在把算法变成程序
实际运行前，就知道为完成一项任务所设计的算法 的好坏，从而运行好的算法，改进差的算法，避免 无益的人力和物力浪费。
算法分析是计算机领域的古老而前沿的课题。
实数(无理数)的算术运算是“不能行”的
8
3）输入
每个算法有0个或多个输入。这些输入是在算法 开始之前给出的量，取自于特定的对象集合——定 义域（或值域）
4）输出
一个算法产生一个或多个输出，这些输出是同输入有某种 特定关系的量。
9
5）有穷性
一个算法总是在执行了有穷步的运算之后终止。
计算过程：只满足确定性、能行性、输入、输 出四个特性但不一定能终止的一组规则。 准确理解算法和计算过程的区别： ➢ 不能终止的计算过程：操作系统。 ➢ 算法是“可以终止的计算过程”。 ➢ 算法的时效性：只能把在相当有穷步内 终止的算法投入到计算机上运行。
for i ←1 to n do for j ←1 to n do x ← x +y repeat
repeat (c)
定义： 频率计数：一条语句或一种运算在算法（或程序）体中
的执行次数。
20
一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间
关于导引与基本数据结 构
1
教材
计算机算法基础（第二版）余祥宣等
华中科技大学出版社
参考书：
1.计算机算法设计与分析：王晓东，电子工业出 版社
2.算法分析与设计 ：（美）古德里奇，（美）塔 玛西亚，霍红卫译 人民邮电出版社
课时安排：28+12
考试形式：闭卷
成绩： 平时50%+考试50%
2
序
计算机算法是计算机科学和计算机应用的核心 数据结构+算法 = 程序 算法（algorithm）是一个在有限时间内逐步
√
第三章 贪心方法
√
第四章 动态规划
√
第五章 检索与周游
√
第六章 回溯法
⊙
第七章 分枝-限界
⊙
第八章 NP-问题
?
算法研讨环节
5
第一章 导引与基本数据结构
1.1 算法的定义及特性 1. 什么是算法？
算法如数字、计算一样，是一个基本概念。 算法是解一类确定问题的任意一种特殊的方法。 在计算机科学中，算法是使用计算机解一类问 题的精确、有效方法的代名词： 算法是一组有穷的规则，它规定了解决某一特 定类型问题的一系列运算。
➢
引用了哪些运算
➢
每种运算被执行的次数
➢
该种运算执行一次所花费的时间等。
算法的执行时间=∑Fi*ti
19
频率计数 例： x←x+y
for i ←1 to n do x←x+y
repeat
(a)
(b)
分析：
(a)： x←x+y执行了1次
(b)： x←x+y执行了n次
(c)： x←x+y执行了n2次
确定使用什么样的运算及其执行时间。 从计算时间上，运算的分类：
➢ 时间囿界于常数的运算：
·基本算术运算，如整数、浮点数的加、减、乘、除 ·字符运算 ·赋值运算 ·过程调用等
特点：尽管每种运算的执行时间不同，但一般只花 一个固定量的时间（单位时间）就可完成。
15
2）计算的约定（续） ➢ 其他运算：
事后测试：将算法编制成程序后实际放到计算机上运行， 收集其执行时间和空间占用等统计资料，进行 分析判断——直接与物理实现有关。
18
1）事前分析
目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法的“好坏”。
如何给出反映算法执行特性的描述？
最直接方法：统计算法中各种运算的执行情况，包括：