Skip to content

算法设计与分析

参考资料

基本概念

  • 时空复杂度及其表示
  • 复杂度计算 如序列求和, 放缩, 积分, 递推分析 (迭代 / 差消 / 递归树)
  • 组合优化问题, 可行解满足约束条件, 其中使目标函数最大 / 最小的解为最优解
  • 主定理

形如

\[ T (n) = aT\left (\frac {n}{b}\right) + f (n) \]

其中

  • a ≥ 1 (子问题数量)
  • b > 1 (问题分割比例)
  • f(n) 是非递归部分的复杂度

时间复杂度为

\[ T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{if } f(n) = O(n^{\log_b a - \epsilon}), \epsilon > 0 \\ \Theta(f(n) \log n) & \text{if } f(n) = \Theta(n^{\log_b a} \log^k n), k ≥ 0 \\ \Theta(f(n)) & \text{if } f(n) = \Omega(n^{\log_b a + \epsilon}), \epsilon > 0 \text{ 且 } af\left(\frac{n}{b}\right) ≤ cf(n) \end{cases} \]

分治

  • 子问题与原问题性质相同
  • 子问题独立
  • 最小子问题直接可解
  • 分解 -> 递归 / 迭代求解 -> 子问题综合
  • 子问题间存在联系 -> 减少重复计算优化 (子问题还是可独立计算的!!!)
  • 预处理优化

动态规划

  • \(f (a_1,a_n)\) 最优时要求 \(f(a_x,a_y), 1 \leq x \leq y \leq n\) 最优
  • 求 \(f(n)\) -> 划分 f 中的子问题 -> 求递推方程
  • 滚动数组 / 状态压缩优化空间

贪心

  • 每一步都选最优解
  • 局部最优解 -> 全局最优解
  • 数学归纳证明 / 交换论证 (证明任意最优解都可以不改变最优解的性质时转换为贪心的解)
  • 贪心不适用时考虑限制参数范围或者计算误差

回溯

  • 解为向量, 搜索空间为树, 跳跃搜索
  • 深度优先搜索 / 广度优先搜索
  • 满足条件时扩大解空间, 不满足时回溯
  • 剪枝优化 (拟合目标函数的界)
  • 启发式优化 (根据现有解启发), 排序优化 (预处理) 都是为了先访问更可能的分支
  • 记忆化优化

线性规划

P 与 NP

  • P 问题: 可在多项式时间内解决的问题
  • NP 问题: 可在多项式时间内验证, 但不能在多项式时间内求解的问题
  • NP 完全问题: NP 问题中最难的问题, 如果其中一个问题可以在多项式时间内完成, 那么所有 NP 问题都可以在多项式时间内完成
  • Cook-Levin 定理: NP 完全问题可以在多项式时间内规约到可满足性问题