第一章 基础知识
先修课程：
Ø离散数学
Ø数据结构
Ø高级程序语言
学习算法的意义
•培养“从蛮力到策略”的思维方法
–蛮力法（Brute Force）是一种解决问题的最简单、最直接、最容易理解的方法。
–数学是一种艺术，使人摆脱蛮力计算。
•从计算机应用的角度
–掌握不同的计算领域中的重要算法，具备设计新算法及分析其性能的能力。
•从计算机理论的角度
–算法是计算机科学的基础。
课程主要内容
•分析
学会对算法的时间和空间的复杂性进行分析，掌握提高算法效率的方法和途径。
•设计
对计算机常用算法有一个全盘的了解，掌握通用算法的一般设计方法
课程介绍—本课程学习的算法
•穷举法 — 百鸡问题
•递归和分治 — 二分查找、快速排序
•贪心法 — 最小生成树、最短距离
•回溯 — 迷宫、八后问题
•动态规划
•
分支与限界
1.1 算法的基本概念
Ø程序 = 算法 + 数据结构
Ø算法设计与分析是计算机科学与技术的一个
核心内容….
1.2 算法的定义
•算法的多种定义
–算法就是解决问题的方法。
–Not answers but rather well defined procedures for getting answers.
–算法是解决某一特定问题的一组有穷指令的序列。
–算法是完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法定义：
算法是问题求解的有效策略.是解某一特定问题的一组有穷规则的集合。
算法特征：
1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。
例：不符合确定性的运算
n 5/0
n 将6或7与x相加
n 未赋值变量参与运算
2）可行性
算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。
例：整数的算术运算是“能行”的
实数的算术运算是“不能行”的
3）输入
每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合。
所谓0个输入是指算法本身定出了初始条件。
4）输出
一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。
5）有限性
一个算法总是在执行了有穷步的运算之后终止。
计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。
• 准确理解算法和计算过程的区别：
Ø 不能终止的计算过程：操作系统
Ø 算法是“可以终止的计算过程”
Ø 算法的时效性：只能把在相当有穷步内终止的算法投
入到计算机上运行。
算法的正确性
•数学归纳法(mathematical induction)
–当n = 1时，这个算法是正确的；
–假设n = k 时，这个算法是正确的，那么当n = k+1时，这个算法也是正确的。
•反例：能够使算法运行失败的输入实例。
1.2 算法复杂性分析
•算法分析 = 分析算法复杂性
•算法复杂性：算法运行所需要的计算机资源的量
–时间复杂性：需要时间资源的量
–空间复杂性：需要空间资源的量
•采用一种与算法外部因素无关的测量方法，只依赖于问题规模、输入以及算法本身的函数
1.2.1 算法的时间复杂性
Ø 算法的输入规模和运行时间的阶
算法的执行时间随问题规模的增大而增大，故
常用关于问题规模n的函数估算算法在大规模问题时的运行时间。
（1）运行时间T(n)的估算
Ø运行时间T(n)的估算
假设初等操作计算模型：所有操作数都具有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。
如：算术运算；比较和逻辑运算；赋值运算(含遍历表和指针赋值）等。
例1.3 估算算法1.1的运行时间T1(n)。
void childen_question(int n,int &k,int g[],int m[],
int s[])
{
int a,b,c;
k=0; //1
for(a=0; a<=n; a++) //1+2(n+1)
for(b=0; b<=n; b++) // n+1+2 (n+1)2
for(c=0; c<=n; c++) // (n+1)2 +2(n+1)3
if(!(c%3)&&a+b+c==n &&
//14(n+1)3 5*a+3*b+c/3==n)
{
g[k]=a; m[k]=b; s[k]=c;
k++; //4(n+1)3
}
}
1.2.2时间复杂性的表示方法
•f(n)是某算法的运行时间函数，g(n)是某一简单函数，当且仅当存在正的常数c和非负整数n0，当n≥n0时：
–如果有f(n)≤cg(n)，则称f(n)当n充分大时上有界；且g(n)是它的一个上界，记作f(n) = O(g(n))。或称f(n)的阶不高于g(n)的阶。
–如果有f(n)≥cg(n)，则称f(n)当n充分大时下有界；且g(n)是它的一个下界，记作f(n) = Ω(g(n))。或称f(n)的阶不低于g(n)的阶。
–当且仅当f(n)=O(g(n))且f(n)= Ω(g(n))时，称g(n)为f(n)的准确界，记作f(n) = Θ(g(n))。或称f(n)与g(n)同阶。
–如果对于任意给定的ε>0，都存在正整数n0，使得当n ≥ n0时有f(n)/g(n)< ε，则称g(n)为f(n)的绝对上界，记作f(n) = o(g(n))。或称f(n)当n充分大时的阶比g(n)低。
常见的时间复杂度
•O(1) ：几乎不存在
•O(logn)：不能考虑全部输入
•O(n)：遍历、扫描全部输入
•O(nlogn)：许多分治算法
•O(n2 )：两层循环
•O(n3) ：三层循环
•O(2n ) ：一个集合的所有子集
•O(n!) ：一个集合中的元素的所有组合
•从算法运行时间上可把算法分为两类
–多项式时间算法(polynomial time algorithm)
•可用多项式来对运行时间限界的算法
•O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
–指数时间算法(exponential time algorithm)
•运行时间用指数函数限界的算法
•O(2n)<O(n!)<O(nn)
1.2.3 时间复杂度分析的步骤
1）确定用来表示问题规模的变量；
2）确定算法的基本操作；
3）写出基本操作执行次数的函数（运行时间函数）；
4）如果函数依赖输入实例，则分情况考虑：最坏情况、最好情况、平均情况；
5）只考虑问题的规模充分大时函数的增长率，用渐近符号O 、Θ、Ω 、o来表示。
6）常用O和Θ
基本操作的定义
–基本操作:算法中的某个初等操作，如果它的最高执行频率和所有其它初等操作的最高执行频率，相差在一个常数因子之内，就说这个初等操作是一个基本操作。
l
基本操作的选择，必须反映出该操作随着输入 规模的增加而变化的情况。
一般：
l检索和排序问题，可选元素比较操作作为基本操作
l矩阵乘法问题，可选数乘作为基本操作
l遍历链表问题，可选设置或更新链表指针作为基本操作
l图的遍历问题，可选访问图中的顶点的操作作为基本操作
一般：先确定基本操作，再利用Ｏ、Ω 、或 Ө，去寻找执行该基本操作的阶，也是算法运行时间的阶。
算法的运行时间
Ø循环次数的统计
算法的运行时间常和算法中的循环次数成正比。
因此，统计算法的循环次数，它的阶可作为算法的运行时间阶。
最好情况、最坏情况、平均情况分析
有些算法的运行时间除与问题规模有关外，还与输
入元素的初始排列顺序有关。因此，有3种分析方法：
最好情况：依据输入元素顺序，算法所达到的最短运
行时间。
最坏情况：依据输入元素顺序，算法所达到的最长运
行时间。
平均情况：算法的运行时间取算法所有可能输入的平
均运行时间。
1.2.4算法的时间复杂性分析
算法的空间复杂性，指的是为解一个问题实例而需
要的存储空间。有两种分析方法：
Ø算法所需的工作空间
不包含存储输入数据、程序代码和常数的空间，
仅包含算法函数体内新生成的变量空间。
Ø程序运行所需的工作空间
包含存储输入数据、程序代码和常数的空间，以及含算法函数体内新生成的变量空间。
1.2.5 最优算法
对解同一问题的多个算法，最优算法是指具有最小时
间复性的算法。
具有最优复杂性的算法都称为最优算法。
最优算法中的各算法按高阶系数判断最短执行时间。
