算法设计与分析

第一章算法概述

任课教师：徐连诚

关于本课程

课程目的：计算机算法设计与分析导引
- 不是一门试验或程序设计课程
- 也不是一门数学课程
教材：计算机算法设计与分析-王晓东
授课：徐连诚，lchxu@163.com，87601
前导课：数据结构+程序设计
授课形式：每周3~4课时+作业+期中/末考试
参考资料：
- Web资源
- 图书资源

算法与程序

算法：是满足下述性质的指令序列。
- 输入：有零个或多个外部量作为算法的输入。
- 输出：算法产生至少一个量作为输出。
- 确定性：组成算法的每条指令清晰、无歧义。
- 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
程序：
- 程序是算法用某种程序设计语言的具体实现。
- 程序可以不满足算法的性质(4)即有限性。
- 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

算法与数据结构

描述算法可以有多种方式
- 自然语言方式、表格方式、图示形式等
- 本书将采用C++与自然语言相结合的方式
算法与数据结构的关系
- 不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；
- 反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。
算法＋数据结构＝程序

表达算法的抽象机制(1)

1.从机器语言到高级语言的抽象
- 高级程序设计语言的主要好处是：
  - 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；
  - 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；
  - 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；
  - 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。

表达算法的抽象机制(2)

2.抽象数据类型
- 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。
- 抽象数据类型带给算法设计的好处有：
  - 算法顶层设计与底层实现分离；
  - 算法设计与数据结构设计隔开，允许数据结构自由选择；
  - 数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；
  - 用抽象数据类型表述的算法具有很好的可维护性；
  - 算法自然呈现模块化；
  - 为自顶向下逐步求精和模块化提供有效途径和工具；
  - 算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。

描述算法与算法设计(1)

描述算法可以有多种方式，如自然语言方式、图形表格方式等。在这里，我们将采用C++语言来描述算法。
C++语言的优点是类型丰富、语句精炼，具有面向对象和面向过程的双重优点。
用C++来描述算法可使整个算法结构紧凑、可读性强。
在课程中，有时为了更好地阐明算法的思路，我们还采用C++与自然语言相结合的方式来描述算法。
算法设计方法主要有：分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。

描述算法与算法设计(2)

问题求解(Problem Solving)

算法分析的基本原则(1)

1.正确性
- 定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。
- 正确性证明的内容：
  - 方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。
  - 程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。
- 程序正确性证明的方法：
  - 大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。
  - 小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。

算法分析的基本原则(2)

2.工作量——时间复杂性分析
- 计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数。
- 基本运算的选择：根据问题选择适当的基本运算。

算法分析的基本原则(3)

3. 占用空间——空间复杂性分析
- 两种占用：
  - 存储程序和输入数据的空间
  - 存储中间结果或操作单元所占用空间——额外空间
- 影响空间的主要因素：
  - 存储程序的空间一般是常数(和输入规模无关)
  - 输入数据空间为输入规模O(n)
- 空间复杂性考虑的是额外空间的大小
- 如果额外空间相对于输入规模是常数，称为原地工作的算法。

算法分析的基本原则(4)

4. 简单性
- 含义：算法简单，程序结构简单。
- 好处：
  - 容易验证正确性
  - 便于程序调试
- 简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。
5. 最优性
- 含义：指求解某类问题中效率最高的算法
- 两种最优性
  - 最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。
  - 平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。

算法分析的基本原则(5)

寻找最优算法的途径 (以最坏情况下的最优性为例)
- 设计算法A，求W(n)。相当于对问题给出最坏情况下的一个上界。
- 寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算。相当于对问题给出最坏情况下所需基本运算次数的一个下界。
- 如果W(n)=F(n)，则A是最优的。
- 如果W(n)>F(n)，A不是最优的或者F(n)的下界过低。
  - 改进A或设计新算法A’使得W’(n)<W(n)。
  - 重新证明新下界F’(n)使得F’(n)>F(n)。
  - 重复以上两步，最终得到W’(n) = F’(n)为止。

算法分析的基本原则(6)

例：在n个不同的数中找最大的数。
基本运算：比较
算法：Find Max
输入：数组L,项数 n11
输出：L中的最大项MAX

{
MAX←L(1); i←2;
while i≤n do
if MAX<L(i) then MAX←L(i);
i←i+1;
end.
}

算法分析的基本原则(7)

行3的比较进行n－1次，故W(n) = n－1。
定理：在n个数的数组中找最大的数，并以比较作为基本运算的算法类中的任何算法最坏情况下至少要做n－1次比较。
证：因为MAX是唯一的，其它的n－1个数必须在比较后被淘汰。一次比较至多淘汰一个数，所以至少需要n－1次比较。
结论：Find Max算法是最优算法。

算法复杂性分析(1)

算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。
一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函数名当中）
- 算法复杂性 = 算法所需要的计算机资源
- 算法的时间复杂性T(n)；算法的空间复杂性S(n)。
- 其中n是问题的规模（输入大小）。

算法复杂性分析(2)

以上分别是最坏情况下、最好情况下和平均情况下的时间复杂性。
其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到TMax(N)的合法输入；I-是DN中使T(N, I-)达到TMin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。

算法复杂性分析(3)

函数的渐进性态与渐进表达式：一般来说，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞。
对于T(N)，如果存在函数T'(N)，使得当N→ ∞使有(T(N)-T'(N))/T(N) →0，那么我们就说T'(N)是T(N)当N→ ∞时的渐进性态。
在数学上，T'(N)是T(N)当N→ ∞时的渐进表达式。
例如：3N2+4NlogN+7与3N2。

算法复杂性分析(4)

算法复杂性在渐近意义下的阶：
- 渐近意义下的记号：O、Ω、θ、o、ω
- 设f(N)和g(N)是定义在正数集上的正函数。
- O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。
- 根据O的定义，容易证明它有如下运算规则：

算法复杂性分析(5)

Ω的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。
θ的定义：定义f(N)=θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。此时称f(N)与g(N)同阶。
o的定义：对于任意给定的ε>0，都存在正整数N0，使得当N≥N0时有f(N)/Cg(N)<ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)).例如，4NlogN+7=o(3N2+4NlogN+7)。
ω的定义：ω(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有n≥n0有：0≤cg(n)<f(n)}f(n)/g(n),as

算法复杂性分析(6)

渐近分析记号的若干性质

（1）传递性：

f(n)=θ(g(n))，g(n)=θ(h(n)) → f(n)=θ(h(n))；
f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n)) → f(n)=Ｏ(h(n))；
f(n)=Ω(g(n))，g(n)=Ω(h(n)) → f(n)=Ω(h(n))；
f(n)=ｏ(g(n))，g(n)=ｏ(h(n)) → f(n)=ｏ(h(n))；
f(n)=ω(g(n))，g(n)=ω(h(n)) → f(n)=ω(h(n))；

（2）反身性：

f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)).

算法复杂性分析(7)

（3）对称性：

f(n)=θ(g(n)) <==> g(n)=θ(f(n)) .

（4）互对称性：

f(n)=Ｏ(g(n)) <==> g(n)=Ω(f(n)) ；f(n)=ｏ(g(n)) <==> g(n)=ω(f(n)) ；

（5）算术运算：

Ｏ(f(n))+Ｏ(g(n)) = Ｏ(max{f(n),g(n)}) ；
Ｏ(f(n))+Ｏ(g(n)) = Ｏ(f(n)+g(n)) ；Ｏ(f(n))*Ｏ(g(n)) = Ｏ(f(n)*g(n)) ；
Ｏ(cf(n)) = Ｏ(f(n)) ；g(n) = Ｏ(f(n)) → Ｏ(f(n))+Ｏ(g(n)) = Ｏ(f(n)) 。

算法复杂性分析(8)

规则Ｏ(f(n))+Ｏ(g(n)) = Ｏ(max{f(n),g(n)}) 的证明
- 对于任意f1(n) ∈ Ｏ(f(n)) ，存在正常数c1和自然数n1，使得对所有n ≥ n1，有f1(n) ≤ c1f(n) 。
- 类似地，对于任意g1(n) ∈ Ｏ(g(n))，存在正常数c2和自然数n2，使得对所有n ≥ n2，有g1(n) ≤ c2g(n) 。
- 令c3=max{c1, c2}，n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。则对所有的n ≥ n3，有

算法复杂性分析(9)

取整函数

取整函数的若干性质

算法复杂性分析(10)

算法分析中常见的复杂性函数

算法复杂性分析(11)

小规模数据复杂性增长图

算法复杂性分析(12)

中等规模数据复杂性增长图

小结

程序与算法
渐进表达式
程序复杂性
习题：
- 1.4、1.10

算法设计与分析

第一章 算法概述

任课教师：徐连诚

关于本课程

算法与程序

算法与数据结构

表达算法的抽象机制(1)

表达算法的抽象机制(2)

描述算法与算法设计(1)

描述算法与算法设计(2)

算法分析的基本原则(1)

算法分析的基本原则(2)

算法分析的基本原则(3)

算法分析的基本原则(4)

算法分析的基本原则(5)

算法分析的基本原则(6)

算法分析的基本原则(7)

算法复杂性分析(1)

算法复杂性分析(2)

算法复杂性分析(3)

算法复杂性分析(4)

算法复杂性分析(5)

算法复杂性分析(6)

算法复杂性分析(7)

算法复杂性分析(8)

算法复杂性分析(9)

算法复杂性分析(10)

算法复杂性分析(11)

算法复杂性分析(12)

小结

第一章算法概述