一、算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法
3
提纲
一、算法与程序 二、算法复杂性分析 三、用C++语言描述算法的方法
4
1.1 算法的概念
算法是指解决问题的方法和过程。 算法是对特定问题求解步骤的一种描述，
包含操作的有限规则和操作的有限序列。 通俗一点讲，算法就是一个解决问题
10
对算法的学习包括五个方面的内容： ① 设计算法。 ② 表示算法。 ③确认算法。 ④ 分析算法。 ⑤ 验证算法。
11
① 设计算法。算法设计工作是不可能 完全自动化的，应学习了解已经被实 践证明是有用的一些基本的算法设计 方法，这些基本的设计方法不仅适用 于计算机科学，而且适用于电气工程、 运筹学等领域；
<b1,...,bn>output,a1,...,an= b1,...,bn}
15
1.3 算法示例—插入排序算法
算法的思想：扑克牌游戏
a0,...,n-1 = 5,2,4,6,1,3 a0,...,n-1 = 5,2,4,6,1,3 a0,...,n-1 = 2,5,4,6,1,3 a0,...,n-1 = 2,4,5,6,1,3 a0,...,n-1 = 2,4,5,6,1,3 a0,...,n-1 = 1,2,4,5,6,3 a0,...,n-1 = 1,2,3,4,5,6
计算机算法设计与分析
Design and Analysis of Computer Algorithms
第一章 算法概述
学习要点:
•理解算法的概念。 •理解什么是程序，程序与算法的区别和内在联系。 •掌握算法的计算复杂性概念。 •掌握算法渐近复杂性的数学表述。 •掌握用C++语言描述算法的方法
2
提纲
一个算法面向一类问题，而不是仅求解问题的一个或几 个实例。
输入
Algorithm
输出
Input
Output
14
1.2 问题表示
例如，排序（SORT）问题定义如下：
－Input=<a1,....,an> ai是实数 －output=<b1,....,bn> bi是实数,且b1...bn －R=(<a1,...,an>,<b1,...,bn>)<a1,...,an>Input，
② 表示算法。描述算法的方法有多种 形式，例如自然语言和算法语言，各 自有适用的环境和特点；
12
③确认算法。算法确认的目的是使人们确信这一算 法能够正确无误地工作，即该算法具有可计算性。 正确的算法用计算机算法语言描述，构成计算机程 序，计算机程序在计算机上运行，得到算法运算的 结果；
④ 分析算法。算法分析是对一个算法需要多少计算 时间和存储空间作定量的分析。分析算法可以预测 这一算法适合在什么样的环境中有效地运行，对解 决同一问题的不同算法的有效性作出比较；
(3).算法代表了对问题的解，而程序则是算 法在计算机上的特定的实现。一个算法若 用程序设计语言来描述，则它就是一个程 序.
8
算法≠程序 算法描述：自然语言，流程图，程序设计 语言，伪代码 用各种算法描述方法所描述的同一算法， 该算法的功用是一样的，允许在算法的描述 和实现方法上有所不同。 本书中采用类C++伪代码语言描述算法
16
算法描述
1. 从第一个元素开始，该元素可以认为已 经被排序
2. 取出下一个元素，在已经排序的元 素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素， 将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素 小于或者等于新元素的位置
5. 将新元素插入到该位置中 6. 重复步骤2
9
人们的生产活动和日常生活离不开算法， 都在自觉不自觉地使用算法，例如人们到 商店购买物品，会首先确定购买哪些物品， 准备好所需的钱，然后确定到哪些商场选 购、怎样去商场、行走的路线，若物品的 质量好如何处理，对物品不满意又怎样处 理，购买物品后做什么等。以上购物的算 法是用自然语言描述的，也可以用其他描 述方法描述该算法。
算法是脱离具体的计算机结构和程序设计 语言的。
7
算法与程序的区别与联系
(1).一个程序不一定满足有穷性。例操作系 统，只要整个系统不遭破坏，它将永远不 会停止，即使没有作业需要处理，它仍处 于动态等待中。因此，操作系统不是一个 算法。
(2).程序中的指令必须是机器可执行的，而 算法中的指令则无此限制。
的时间也是有限的。
算法要求其执行时间是有限的 (终止性) 。 程序的执行时间可能是无限的。(例操作系统，只
要整个系统不遭破坏，它将永远不会停止，即使 没有作业需要处理，它仍处于动态等待中。因此， 操作系统不是一个算法。 )
6Hale Waihona Puke 程序程序是某个算法或过程的在计算机上的一 个具体的实现。
程序是依赖于程序设计语言的，甚至依赖 于计算机结构的。
⑤ 验证算法。用计算机语言描述的算法是否可计算、 有效合理，须对程序进行测试，测试程序的工作由 调试和作时空分布图组成。
13
1.2 问题表示
设Input和Output是两个集合。一个问题是一个关系 RInputOutput，Input称为问题R的输入集合，Input的 每个元素称为R的一个输入，Output称为问题R的输出或 结果集合，Output的每个元素称为R的一个结果。
的公式（数学手册上的公式都是经典算 法）、规则、思路、方法和步骤。算法可 以用自然语言描述，也可以用流程图描述， 但最终要用计算机语言编程，上机实现。
5
算法是若干指令的有穷序列，满足性质：
输入： 有1个或多个满足给定约束条件的量作为算法的输入。 输出： 算法产生至少一个量作为输出。 确定性：组成算法的每条指令是清晰，无歧义的。 有限性：算法中每条指令的执行次数是有限的，执行每条指令
17
1.3 算法示例
插入排序算法
template<class Type> void InsertionSort(Type *a, int n)
// 数组a中包含了n个待排序的数. {
Type key; for (int i = 1; i < n; i++) { key=a[i]; // Insert a[i] into the sorted sequence a[0..i-1].
