目录导学

算法设计思想

• 设计思想：尽量选复杂度低的算法
• 算法实现依赖于数据结构，要选择合适的数据结构
• 实际问题中综合考虑：时空权衡、实现成本权衡

序列求和

• 基本求和公式: 等比数列, 等差数列, 调和数级数
• 估计和式的阶: 放大估计上界; 积分估计下界

递推方程求解

• 主要求解方法

  • 迭代 + 序列求和
  • 递归树 + 求和
  • 主定理（注意条件验证）

• 常见递推方程的解:

$$f(n) = a f\left(\frac{n}{b}\right) + d(n)$$

• a : 归约后的子问题个数
• n/b : 归约后子问题的规模
• d(n) : 归约过程及组合子问题的解的工作量

算法设计技术

主要内容

• 使用条件
• 主要设计步骤
• 时间复杂度分析方法
• 改进途径
• 典型例子

分治策略

• 适用条件: 归约为独立求解子问题

• 设计步骤:

  1. 归约方法（划分均衡、类型相同）
  2. 初始子问题的计算
  3. 子问题解的综合方法

• 改进途径: 减少子问题数; 预处理

• 典型问题: 二分检索，归并排序，芯片测试，幂乘，矩阵乘法，最邻近点对，多项式求值

动态规划

• 适用条件: 优化问题，多步判断求解，满足优化原则，子问题重叠

• 能划分阶段

• 最优化原理（最优子结构性质）: 一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列

• 无后效性原则: 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。一个问题被划分各个阶段之后，阶段k中的状态只能通过阶段k+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系。

• 设计步骤:

  1. 确定子问题边界
  2. 列关于目标函数的递推方程及初值
  3. 自底向上，备忘录存储
  4. 标记函数及解的追踪方法
  5. 复杂度分析：备忘录；递推方程

• 典型问题: 矩阵链相乘，投资，背包，最长公共子序列，图像压缩，最大字段和，最优二分检索树，生物信息学应用（RNA二级结构预测）

贪心法

• 适用条件: 组合优化问题，多步判断求解，有贪心选择性质

• 贪心选择性质: 一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择

• 设计步骤:

  1. 局部优化策略的确定及算法正确性证明（直接证明、数学归纳法、交换论证）
  2. 复杂度分析

• 典型问题: 活动选择，装载问题，最小延迟调度，最优前缀码，最小生成树，单源最短路径

回溯和分支限界

• 适用条件: 搜索问题、优化问题，多步判断求解，满足多米诺性质

• 设计步骤:

  1. 确定解向量（每个分量含义）
  2. 确定搜索树结构与搜索顺序
  3. 结点分支搜索的约束条件与代价函数
  4. 路径存储
  5. 搜索树结点数估计
  6. 复杂度分析：最坏情况下同蛮力算法

• 典型问题: n后问题，背包问题，货郎问题，装载问题，最大团问题，圆排列问题，连续邮资问题