算法在计算中的作用

算法的定义

算法是良定义的计算过程，该过程输入某个值或者集合，产生某组值或集合。

  • 解决问题：对于每个输入实例，算法能够停机。
  • 效率：输入规模比较重要，常系数经常被记法隐藏，在同级算法比较中会有用。
  • 硬件也是程序：后面我们会看到指令执行模型在算法中的体现

数据结构的定义

存储和组织数据的方式。

算法基础

插入排序

循环不变式 loop invariant

  • 初始化 initialization：循环第一次迭代以前，它为真
  • 保持 mantainance：如果循环某次迭代前它为真，那么下次迭代之前它仍为真。
  • 终止 termination：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

我们使用循环不变式来证明了我们用插入排序解决了排序问题。这个方法和数学归纳法的区别是数学归纳法不一定终止，但循环不变式会终止。

分析算法

RAM 模型

在这个模型里，一切都是有限的（limited）：

- 指令只能在常量时间里执行
    - arithmetic 加减乘除
    - 赋值 load
    - 控制
- 数据的字长有限（更广义地讲，内存有限）：我们不能引入无限存储
- **程序单线程执行**
- **不考虑 memory hiarachy**，否则问题会复杂得难以分析

基于这些假定，我们可以用一套伪代码来写所有算法，而且可以用统一的标准来衡量算法之间的复杂度。complexity（算法复杂度） is about step operation metric，我们在有限的资源里寻找合适消耗时间的算法。

插入排序的算法分析

  • 运行时间是输入规模的函数
    • 我们研究的问题不同，输入规模的定义也不同：排序的输入规模是项数，而相乘的输入规模则是位数，图的输入规模是顶点和边的数量
    • 运行时间在我们写灯饰 T(n)=xxx 的时候，意味着我们在计算操作步数的总和

增长量级

我们通常只关心运行时间的增长率和增长量级，所以一个多项式里我们只关注最高阶项的阶数，它表示通用精度。常系数和低阶项我们都不关注，它们表示多余的精度。

设计算法

分治法

  1. 插入排序让我们引入了增量法，构造越来越大的子数组，待其等于主数组时，问题已被解决。
  2. 分治法是让我们递归地重复以下过程：divide-conquer-merge。

当一个算法仅包含对其自身的调用的时候，我们可以使用递归方程来描述运行时间。

该方程根据在较小输入上的运行时间来描述在规模为 n 的问题上的总运行时间然后，我们可以使用数学工具来求解该递归式并给出算法性能的界。

使用递归树来计算 T(n) 的最坏情形：
递归树总是层为 lgn+1，高为 lgn，宽为c的树。假设叶子结点的代价为c。

则除根部以外每层的代价都相等，为 cn（c取归并、分解和单独操作的最大值就能归并c在不同层级之间不一致的问题），则除根部以外的总代价为 宽 高 每层代价 = cnlgn，加上根部 cn（D(n) + C(n)即分解和归并的代价。这种式子能写成c2，和解决子问题的c1取一个最大值c即可进入上界分析问题），总代价为 cnlgn + cn，所以这个算法的时间复杂度上界为 O(lgn)。

从鸽巢问题出发，我们看到什么

动态规划

动态规划的本质，是寻找状态的定义，并基于这个定义给出状态转移的方程。

最优子结构(optimal substructure）

定义

我们通常要做出一组选择来达到最优解。

在做每个选择的同事，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题的时候，动态规划通常就会很有效。其关键技术就是对每个这样的子问题都保存其解。档期重复出现时，可避免重复求解。

programming 其实是一种表格法，而非编程。分治法解决的问题是，互不相交的子问题。

最优解有两种： an optimal solution vs the optimal solution。

步骤

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值，通过自底向上的方法。
  4. 利用计算出的信息，构造一个最优解。

递归是自顶向下求解。
迭代可以自底向上求解。

能够用动态规划来解的问题通常具有两个性质：

  • 最有子结构性质：问题的最优解，是由相关子问题的最优解组合而成，而这些子问题可以独立求解。
  • 子问题重叠性质：最优子结构里可能出现的子问题，可能会产生重叠。

切割钢条问题

一般形式

要做基本的切割分析，得出切割方案的一般形式（因为对称性，我们总可以去掉一部分解），如：

rn = max(pn, r1 + r(n-1),…, rn-1 + r(1))

更进一步推导出具体形式：

rn = max(pn + rn-1)

递归调用树分析

借助递归调用树的节点总数，我们可以估计总调用次数。

需要通过证明，得知 T（n）= 2 的 n 次方（TODO）。

日后可以把它转化为子问题图：

动态规划的两种等价实现方法

动态规划仔细安排求解顺序，对每一个重复的子问题只求解一次，并将结果保存下来。

这是典型的时空权衡问题（time-memory trade-off）。

带备忘的自顶向下方法（top-down with memoization）。

贪心算法

与动态规划相似，贪心算法通常用于最优化问题。我们做出一组选择来达到最优解。贪心算法的四项，是每一步都追求局部最优解。

贪心选择性质的证明总是：假定一个存在一个最优解。最优解中的第一个选择如果可以被替换，替换成另一个贪心选择而能得到【另一个兼容】的最优解，则这个问题具有贪心选择性质。

只能用 dp 来解的问题，通常子问题的解是不能相容的，一个子问题的部分选择无法替换成另一个选择而让解的其他部分不变。贪心算法可以解决分数背包问题，不能解决0-1背包问题。因为0-1背包问题，把价值最高的解替换成功价值次高的解，有可能造成空间的变化，以至于让子问题的规模也得以变大-子问题的解可能也因此上升。

霍夫曼编码

霍夫曼具有贪心算法性质。
霍夫曼编码使用了一种前缀编码（prefix code），即没有任何码字是其他码字的前缀。使用这种前缀码，我们得到一串编码后可以唯一地解析出我们想要的信息，不产生二义性。

变长编码本身是一种变长编码（variable-length code），有点类似于 utf-8。核心思想是让拥有更高出现频率的 character 得到更短的码字。

摊还分析（amortized analysis）

摊还分析只能拿来分析一类特定的算法。摊还分析并不是通过分析每个操作的实际代价的界，来分析操作序列代价的界，而是直接分析序列整体的代价的界。这种方法的一个好处是，虽然某些操作的代价可能很高，但其他很多操作的代价可能很低。

Progamming Checklist

  • 先写防御性编程方案。
  • 然后写提前截断流程的子问题的答案。
  • 开始用递归或者迭代的方式求子问题的解，并逐渐推导到当前问题。