算法基本概念

计算问题

问题(problem)一般描述了期望的输入输出关系，而问题实例(instance)具体化了某一输入

形式化描述

是一种规范的描述计算问题的方法，通过描述一个问题的输入和输出以及相应的约束条件来简洁地描述一个计算问题。例如对于一个排序问题，其形式化描述如下

输入：一个包含n个元素的序列A(a1,…,an)

输出：一个输入序列的排列(a1’,…,an’)，并且满足a1’<=a2’<=…<=an’

算法功能

算法功能

伪代码

伪代码(pseudocode)用于描述算法，并且忽略了具体语言实现的细节，不带有具体语言的风格，但是可以与某些语言相似

《算法导论》中的一些规定

例如循环变量循环结束保留最终值、变量默认为局部变量等，具体可参考《算法导论》

算法正确性

算法正确性的概念

算法正确性包含两方面含义

  • 可以正常停止(指在有限时间内停止运行)
  • 对于任意的输入，总是给出正确的输出

An algorithm is said to be correct if, for every input instance, it halts with the correct output. A correct algorithm solves the given computational problem.

注：不满足正确性性质的算法是不正确的，但是不一定是没有实际用处的，例如随机算法(可能无法正常停止，但一旦停止必然给出正确结果)，概率算法(一定会正常停止，但是不一定给出正确结果)，如果它们的不正确概率是可控的，那么这些算法是有实用价值的。例如如果某随机算法无法正常停止的的概率小于计算机出现故障的概率，那么该随机算法当然是有意义的。

算法正确性的证明

算法正确性需要严格证明，而不能用具体的输入实例验证。算法不正确只需要举出一种不正确的情况即可。

循环不变式

循环不变式即在多次循环迭代中，每一次循环前都正确的性质或者公式。
证明分为三步，可类比数学归纳法，但不完全相同(数学归纳法可一直归纳下去)

  • 初始化：即在第一次迭代开始前，循环不变式为真
  • 保持：假设在某次循环前循环不变式为真，在这次循环结束后，其仍为真
  • 终止：当循环迭代结束之后，循环不变式由上面两条可知仍为真，此时它提供一个有用的性质，帮助证明

注：循环不变式只能用于证明算法中循环语句部分的正确性，如果算法还包含其他部分，不能只用循环不变式证明算法的正确性，其他部分同样要证明，本课程不展开讨论。

算法分析

分析算法运行时间、内存空间，有时还需考虑网络带宽、硬件等

计算模型

计算模型是对算法进行客观评价的评价体系，其描述了实现技术的模型，包括所用资源及其代价。

RAM模型

RAM模型即random-access machine模型，是一种单处理器计算模型，其有以下要求：

  • 假设每行伪代码使用常量时间(不一定相等)，为了分析方便并不精确定义每条指令所用时间，并且这些指令是符合真实计算机中常见指令的，不能滥用RAM模型(指随意设置指令)

    注：RAM模型中计算2k也是常量时间的，因为实际上是位移运算

  • 不对内存层级进行建模，即每次访存都使用一个常数时间步，无论访问位置是否位于Cache
  • 避免使用一些RAM模型中未列出但真实计算机可能有的指令，RAM模型包含算数指令、数据移动指令、控制指令
  • RAM模型包含整型和浮点型数据，并且假定数据字的规模在一个范围内，例如输入规模为n时，整数用clgn(c为常亮且c>=1)位来表示，这样可以保证字长足够能保存n并且字长不会无限大，否则可以在常量时间内对无限大数字操作，这是不现实的

运行时间

影响运行时间的因素

  • 输入规模(input size)
    输入规模可能是输入项个数、数据位数(例如相乘)、多个量描述(图)，需要对具体问题指明
  • 输入数据的分布(distribution)
  • 算法的实现，例如使用什么样的数据结构

运行时间分析方法

  • 假定每行伪代码需要一个常量时间ci
  • 算法运行时间是执行每条语句运行时间总和
  • 最终将ci合并，并只考虑增长最快项，且忽略项首系数

三种运行时间

三种运行时间都是考虑在相同输入规模下，不同数据分布带来的影响

  • 最好运行时间
  • 最坏运行时间
  • 平均运行时间

其中最坏运行时间是任何输入对应运行时间的上界

算法设计

算法设计的基本方法

  • 分治法/Divide and Conquer
  • 贪心算法/Greedy Strategy
  • 动态规划/Dynamic Programming
  • 线性规划/Linear Programming
  • 回溯法/Backtracking
  • 分支定界法/Branch and Bound
  • 其他方法

分治法

分治法一般步骤

  1. Divide:将问题划分成具有相同性质的子问题
  2. Conquer:递归地解决子问题
  3. Combine:将子问题的解组合成原问题的解

分治法举例：Merge Sort

伪代码略,见排序一章

监视哨/Sentinel:在算法中用于简化代码实现，可以在序列的一端放置一个不可能出现的特殊元素，有效避免越界以及多余的比较等

分治法递归方程

设n个元素的问题的运行时间为T(n)，每个问题被分成a个子问题，每个子问题规模为n/b，并且当规模小于等于c时，运行时间变为常数，记为Θ(1)。那么T(n)由以下部分组成：

  1. 分割问题为子问题的时间，记为D(n)
  2. 子问题求解所需要的运行时间aT(n/b)
  3. 将子问题组合成原问题解的时间，记为C(n)

故递推方程为以下形式： T(n) = D(n) + C(n) + aT(n/b) , others = Θ(1) , n <= c

补充内容

调和级数

调和级数指如下形式的和式
$H_n = 1+\frac{1}{2}+…+\frac{1}{n} = \sum_{k=1}^n \frac{1}{k} = ln(n)+O(1)$
即调和级数渐近紧确界为$\Theta (lgn)$

证明

可以采用积分与矩形面积和的方法来建立对数和$\frac{1}{k}$之间的关系
积分与和式

根据上图(来自算法导论附录)，可以得到以下积分与和式的关系(假设f(x)是单调递增的):
$\int_{m-1}^n f(x)dx \leq \sum_{k=m}^n f(k) \leq \int_{m}^{n+1} f(x)dx$

从而对于调和级数$H_n = \sum_{k=1}^n \frac{1}{k}$，有如下不等式(这里对于单调递减函数是同理的):
$\int_{1}^n \frac{1}{x}dx + 1\leq H_n \leq \int_{1}^{n+1} \frac{1}{x}dx$
即$ln(n)+1 \leq H_n \leq ln(n+1)$，很容易证明对于$H_n = \Theta(lgn)$