算法分析与设计

1.1 算法

1. 什么是算法？

算法是解一确定类问题的任意一种特殊的方法。

在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词： 算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。

2. 算法的五个重要特性

确定性、能行性、输入、输出、有穷性/有限性

3）输入

每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域

计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。

准确理解算法和计算过程的区别：

 不能终止的计算过程：操作系统  算法是“可以终止的计算过程”。

 算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行。 1.2 算法描述

算法 = 控制结构 + 原操作

表示算法的语言主要有： 自然语言 流程图 盒图 PAD图 伪代码

计算机程序设计语言 本书中的算法描述约定

采用类似C语言的伪代码描述法 顺序结构：以“；”结束 选择结构：if,switch

循环结构：for,while, do¡­while 数据类型：int,float,double,char 数组： 类型名 数组名[n]; 下标以0开始



模块及接口：main()开始 return(返回信息)

1. 算法分析的目的

通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。

2. 重要的假设和约定

1）计算机模型的假设

 计算机形式理论模型 ：Turing机模型  通用计算机模型：

 单处理器：每次执行程序中一条指令  有足够的“内存”

 能在固定的时间内存取数据单元

2）计算的约定

确定使用什么样的运算及其执行时间。 从计算时间上，运算的分类：

 时间囿界于常数的运算：每种运算的执行时间不同，但一般只花 一个固定量时间（单位时间）就可完成。

¡¤基本算术运算 ¡¤字符运算 ¡¤赋值运算 ¡¤过程调用等 2）计算的约定

 其他运算：特点：运算时间无定量

¡¤字符串操作：与字符串中字符的数量成正比。 ¡¤记录操作：与记录的属性数、属性类型等有关。

如何分析非时间囿界于常数的运算？ 如：Tstring = Length（String）* tchar

算法的执行时间=∑Fi*ti

F是算法中用到的某种运算i的次数， ti是该运算执行一次所用时间。 i

3）工作数据集的选择

编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。

测试数据集的生成在目前算法证明与程序正确性证明没有取得理论上的突破性进展的情况下，是程序测试与算法分析中的关键技术之一。



¡¤作为算法分析的数据集：典型特征

¡¤作为程序性能测试的数据集：对执行指标产生影响的性质

4. 如何进行算法分析？

事前分析：就算法本身，通过对其执行性能的理论分析，

得出关于算法特性——时间和空间的一个特征 函数（Ο、Ω）——与计算机软硬件没有直接 关系。

事后测试：将算法编制成程序后放到计算机上运行，收集

其执行时间和空间占用等统计资料，进行分析 判断——直接与物理实现有关。

1）事前分析

目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法 “好坏”。

如何给出反映算法执行特性的描述？

最直接方法：统计算法中各种运算的执行情况：  运用了哪些运算

 每种运算被执行的次数

 该种运算执行一次所花费的时间 算法的执行时间=∑Fi*ti 算法的输入规模

算法的执行时间随问题规模的增长而增长，增长的速度随不同的算法而不同 没有一个方法可以准确的计算算法的具体执行时间 语言、编译系统、计算机

实际上，在评估算法的性能时，并不需要对算法的执行时间作出准确的统计，人们希望算法与实现的语言无关、与执行的计算机无关

所关心的是：算法的执行时间，随着输入规模的增长而增长的情况

 计算时间/频率计数的表示函数

通过事前分析给出算法计算时间（频率计数）的一个函数表示形式，一般记为与输入规模n有关的函数形式：f(n)

注：最高次项与函数整体的关系

空间特性分析（与时间特性的分析类似，略）

2）事后测试

目的：运行程序，确定程序实际耗费的时间与空间，验证先前的分析结论——包括正确性、执行性能等，比较、优化所设计的算法。 分析手段：作时、空性能分布图。 5. 计算时间的渐近表示 记：算法的计算时间为f(n)

数量级限界函数为g(n) 其中，

 n是输入或输出规模的某种测度。



f(n)表示算法的“实际”执行时间—与机器及语言有关。

mn

 g(n)是形式简单的函数，如n，logn，2，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的与机器及语言无关的函数。

以下给出算法执行时间：上界（О）、下界（Ω）、¡°平均¡±（ ）的定义。 渐进意义下的记号：O,Ω,

定义1.1 如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。

多项式定理:

定理1.1 若A(n) = amnm+¡­+a1n+a0是一个m次多项 式，则有A(n)=Ο(nm)

即：变量n的固定阶数为m的任一多项式，与此多 项式的最高阶nm同阶。 证明：取n0=1,当n≥n0时，有

|A(n)|≤|am|nm+…+|a1|n+|a0|

≤(|am|+|am-1|/n+…+|a0|/nm) nm ≤(|am|+|am-1|+…+|a0|) nm 令c= |am|+|am-1|+…+|a0| 定理得证。 • 算法分类（计算时间）

多项式时间算法：可用多项式（函数）对其计算时间限界的算法。 常见的多项式限界函数有：

Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3) 指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： Ο(2n) < Ο(n！) < Ο(nn)

说明：当n取值较大时，指数时间算法和多项式时间 算法在计算时间上非常悬殊。

含义：

如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(N)|的一个常数倍。所以g(N)是计算时间f(N)的一个下界函数。 f(n)的增长至少像g(n)的增长那样快

试图求出¡°最大¡±的g(N)，使得f(N) = Ω(g(N))。

定义1.3 如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N))

含义：

算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作： 既有f(N)=Ω(g(N))，又有f(N)=Ο(g(N))

NP完全问题（1）

NP完全性问题属于“计算复杂性”研究的课题。也就是计算机求解问题的难易程度



P

类问题是所有复杂度为多项式时间的问题的集合。一般称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。

可以在多项式时间内验证一个解是否正确的问题称为NP问题。象推销员旅行等问题，至今未找到多项式时间算法解的一类问题，称之为NP类问题。 NP完全问题（2）

NP完全性问题：由于“P=NP是否成立”这个问题难以解决，从NP类问题中分出复杂度最高的一个子类，称为NP完全类。已经证明，任取NP类中的一个问题，再任取NP完全类中的一个问题，则一定存在一个具有多项式时间复杂性的算法，可以把前者转变为后者，即只要能证明NP完全类中有一个问题属于P类的，也就证明NP类中所有问题都是P类的 NP完全问题的解决方法 研究具体实例的特殊性 动态规划和分支限界方法 概率分析 近似算法 启发式算法

6. 算法分析实例

一个具体算法的时间复杂度和空间复杂度往往不，在算法设计中要在时间效率和空间效率之间折衷。 非递归算法分析

a．仅依赖于问题规模的时间复杂度

有一类简单的问题，其操作具有普遍性，也就是说对所有的数据均等价地进行处理。 小结

理解什么是算法；算法特性；

理解问题求解的步骤及算法在其中的重要地位； 理解算法的计算复杂性概念；

掌握算法复杂度分析的一般方法和数学表示； 学会算法设计基本技巧； 学会对算法进行分析。

3.1 循环与递归

设计算法重复处理大量数据的思路：以不变应万变； 两种思路：循环、递归。 3.2 算法与基本数据结构 小结

理解循环与递归的意义；

理解算法与数据结构的关系。

掌握循环和递归的基本使用方法； 掌握算法设计中对数据结构的选择。

迭代算法

也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。一般用于数字计算，累加、累乘等都是其应用。 设计工作分为3步 （1）确定迭代模型 （2）建立迭代关系式

（3）对迭代过程进行控制

蛮力法 1 枚举法

3 蛮力法的优点

可以用来解决广阔领域的问题；

对于一些重要的问题，它可以产生一些合理的算法； 解决问题的实例很少时，它让你花费较少的代价； 可以解决一些小规模的问题；

可以作为其他高效算法的衡量标准。 小结

掌握蛮力法的基本思想：蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义； 掌握蛮力策略的具体应用；

蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。

分治算法 1 排序问题

2 分治算法框架 3 二分法

4 二分法变异 5 同题异策

2 分治算法框架-1 算法设计思想：

将整个问题分解成若干个小问题后分而治之。

如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

分治法的基本步骤在每一层递归上都有三个步骤：

1)分解：将原问题分解为若干个规模较小，相互，与原问题形式相同的子问题； 2)解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；

3)合并：将已求解的各个子问题的解，逐步合并为原问题的解。 2 分治算法框架-2

有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后(最小)的子

问题的解。分治法的这类应用，又称为 “减治法”。 多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如归并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。 2 分治算法框架-3

适合用分治法策略的问题：

当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。

1)能将这n个数据分解成k个不同子集合，且得到k个子集合是可以求解的子问题，其中1＜k≤n；

2)分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制； 3)求出这些子问题的解之后，就可推解出原问题的解； 1 例排序问题-先进的排序方法 快速排序 堆排序(略) 归并排序

3 例2 金块问题

金块问题：老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。

3 例3 残缺棋盘

kk

残缺棋盘是一个有2×2 (k≥1)个方格的棋盘，其中恰有一个方格残缺。 下图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

4 最大子段和

例5 求数列的最大子段和。

给定n个元素的整数列(可能为负整数)a1，a2，…，an，求形如ai，ai+1，aj，i，j=1，2，…，n，i<=j的子段，使其和为最大。

例如，当(a1, a2, a3, a4, a5, a6)=(-2, 11, -4, 13, -5, -2) 4 例6 大整数乘法 例6 大整数乘法。

请设计一个有效的算法，可以进行两个n位大整数的乘法运算。 小结

理解分治算法的概念和基本思想；

通过应用范例学习分治策略，掌握分治算法的设计步骤和基本框架； 理解各种问题的具体算法。

贪婪算法

1 贪婪算法的思想 2 可绝对贪婪问题 3 相对贪婪问题 4 问题的复杂性 5 贪婪算法实例 1 贪婪算法的思想

贪婪算法(贪心算法)的根本思想：

2. 贪心方法的一般策略

问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。 1）一般方法

根据题意，选取一种量度标准。然后按照这种量度标准对n个输入排序，并按序一次输入一个量。

如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2）贪心方法

这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 注：

 贪心解 最优解

 直接将目标函数作为量度标准也不一定能够得到问题的最优解

3）使用贪心策略求解的关键

选取能够得到问题最优解的量度标准。 背包问题 1.问题的描述

已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn) ，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效益，这里，0≤ xi ≤1, pi >0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ 分析：

① 装入背包的总重量不能超过M

② 如果所有物品的总重量不超过M，即 ≤M，则把所有的物品都装入背包中将获得最大可能的效益值

③ 如果物品的总重量超过了M，则将有物品不能（全部）装入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为M的若干物品（整个或一部分）

目标：使装入背包的物品的总效益达到最大。

1 贪婪算法的思想-例1-问题分析 例1 币种统计问题

某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。 1 贪婪算法的思想-例2 活动安排问题

 n个活动E={1,2,..,n}，都要求使用同一公共资源（如演讲会场等）。且在同一时间仅一个活动可使用该资源。

i[si,fi), si为起始时间, fi为结束时间。si=fj或sj > =fi

活动安排问题:求最大的相容活动子集合。

---尽可能多的活动兼容使用公共资源。 2 可绝对贪婪问题-例3

例3 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 输出应包括所去掉的数字的位置和组成的新的正整数(N不超过100位)。

3 相对贪婪问题-例6-取数游戏 3 相对贪婪问题-例7-多机调度问题 6 单源点最短路径

1. 问题描述

 最短路径问题：

● 每对结点之间的路径问题 ● 特定线路下的最短路径问题 ● 单源最短路径问题等

 单源最短路径问题

已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。

假定边的权值为正。

例 求下图中从v1出发到其余各结点的最短路径

算法的执行轨迹描述

3. 最短路径生成树

对于无向连通图G，由结点v到其余各结点的最短路径的边构成G的一棵生成树，称为最短路径生成树。

注：不同起点v的生成树可能不同。 小结

理解贪心算法的概念；掌握贪心算法的基本思想。 掌握贪心算法的基本要素 （1）贪心选择性质 （2）最优子结构性质

理解可绝对贪婪问题和相对或近似贪婪问题。

理解贪心算法的一般理论；通过应用范例学习贪心设计策略。 理解各种问题的具体算法。

数塔问题

例1 数塔问题

有形如右图的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。 3 动态规划的手工计算

5 动态规划的思想和概念-基本思想 动态规划的基本思想

 动态规划方法的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个子问题就是初始问题的解。 5 -主要概念

阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。

状态：某一阶段的出发位置称为状态。通俗地说状态是对问题在某一时刻的进展情况的数学描述。

决策：从某阶段的一个状态演变到下一个阶段某状态的选择。

状态转移方程：根据上一阶段的状态和决策导出本阶段的状态。这就像是“递推”。 5 -主要概念-数塔问题

阶段：每行就是一个阶段； 5 -适合解决的问题的性质

动态规划算法的问题及决策应该具有两个性质：最优化原理、无后向性。 1) 最优化原理( 或称为最佳原则、最优子结构) ；

2) 无后向性( 无后效性) ：某阶段状态一旦确定以后，就不受这个状态以后决策的影响。即

某状态以后的过程不会影响以前的状态，只与当前状态有关。 5 -设计步骤

设计动态规划算法的基本步骤

设计一个标准的动态规划算法的步骤： 1) 划分阶段； 2) 选择状态；

3) 确定决策并写出状态转移方程。 例2 资源分配问题

设有资源n(n为整数),分配给m个项目,gi(x)为第i个项目分得资源x(x为整数)所得到的利润。 求总利润最大的资源分配方案，也就是解下列问题： max z=g1(x1)+ g2(x2)+……gm(xm) x1+x2+x3+……xm = n，0≤xi≤n，i=1,2,3,……,m 函数gi(x)以数据表的形式给出。 例2 例2 例2

例3 n个矩阵连乘问题 矩阵可乘？

矩阵只有当左边矩阵的列数等于右边矩阵的行数时，它们才可以相乘，乘积矩阵的行数等于左边矩阵的行数，乘积矩阵的列数等于右边矩阵的列数。 可乘矩阵相乘怎么乘？

矩阵的乘积是左行乘右列。

实例：X=“A,B,C,B,D,A,B”和Y=“B,D,C,A,B,A” j 0 1 2 3 4 5 6 i yi B D C A B A 0 xi 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 1 2 2 3 3 4 7 B 0 1 2 2 3 4 4

5.6 0/1背包问题 1. 问题描述

1) KNAP(1,j,X)

目标函数：

约束条件：

0/1背包问题：KNAP(1,n,M) 最优性原理对于0/1背包问题成立 求解策略：向前递推、向后递推

2) 向后递推关系式

记fj(X)是KNAP(1,j,X)的最优解，则fn(M)有 fn(M) = max{fn-1(M),fn-1(M-wn)+pn} 对于任意的fi(X)，i＞0,有

fi(X) = max{fi-1(X),fi-1(X-wi)+pi} 递推过程：

★初始值

0 X≥0 f0=

－∞ X＜0 ★求出fi在所有可能的X取值情况下的值。 ★ fn(M)=KNAP(1,n,M)

例2 例1的序偶计算

n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 S0={(0,0)} ={(1,2)} S1={(0,0),(1,2)} ={(2,3),(3,5)} S2={(0,0),(1,2), (2,3),(3,5)}

={(5,4),(6,6), (7,7),(8,9)} S3={(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9)} 注：序偶(3,5)被(5,4)“支配”而删除 例2

S0={(0,0)}

S1={(0,0),(1,2)}

S2={(0,0),(1,2), (2,3),(3,5)}

S3={(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9)}

M=6，f3(6)由S3中的序偶(6,6)给出。 1) ∵(6,6) S2 ∴x3=1

2) ∵(6-p3,6-w3)=(1,2)∈S2且(1,2)∈S1 ∴x2=0 3) ∵(1,2) S0 ∴x1=1 小结

理解动态规划算法的概念和基本思想； 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）无后效性

体现动态规划算法优势的性质－重叠子问题性质

通过应用范例学习动态规划策略，掌握动态规划算法的设计步骤和基本框架； 理解各种问题的具体算法。

一、图搜索概论 1 树与图的回顾

树和图的定义、基本术语 图的存储结构

树和图的遍历方法 2 显式图&隐式图

3 图搜索术语&方法分类 二、广度优先搜索

1 图的广度优先遍历/搜索算法 2 广度优先搜索的应用

例1 求经过城市最少的路线问题 例2 走迷宫问题

三、深度优先搜索 1 深度优先搜索

深度优先与广度优先的策略比较：  区别在于扩展结点的过程；

 广度优先搜索，扩展E- 结点的所有邻接点，E- 结点就成为一个死结点。一个结点只有一次成为“活结点”。

 深度优先搜索，扩展的是E- 结点的邻接结点中的一个，并将其作为新的E- 结点继续扩展；当前E- 结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。一个结点可能多次成为“活结点”。 4 双连通分图与深度优先检索

【通信网】图中结点表示通信站，边表示通信线路。

基本概念

问题解的n元组表示 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点