学习笔记-算分期中复习

复杂度分析

• 函数的阶

  \(n!\sim \Theta(\sqrt{n}(\frac{n}{e})^n)\).

  于是 \(\log n!\sim \log (\frac{n}{e})^n\sim n\log n\).

• Master Theorem

  \(T(n)=aT(n/b)+f(n)\)

  1. 若 \(f(n)=O(n^{\log_ba-\epsilon})\)，则 \(T(n)=O(n^{\log_b a})\).
  2. 若 \(f(n)=\Theta(n^{\log_b a})\)，则 \(T(n)=O(n^{\log_b a}\log n)\).
  3. 若 \(f(n)=\Omega(n^{\log_b a}+\epsilon)\)，且对于某个常数满足任意充分大 \(n\) \(af(b/n)\le cf(n)\)，则 \(T(n)=\Theta(f(n))\).

动态规划

• 最优子结构：问题的最优解蕴含着子问题的最优解.
• 重叠子问题：递归中为数不多的子问题被重复计算.
• 解答：目标函数，递推方程，边界条件，正确性证明，标记函数

贪心

• 正确性证明：归纳；交换论证：从一个最优解逐步进行结构变换得到贪心最优解.

回溯法

• 解向量：将解表示成一个 \(x\) 维向量.

• 搜索空间：一棵树，树叶表达可行解，每个节点代表了部分解向量.

  完全 \(m\) 叉树？排列树？

• 部分向量：节点所代表的东西，eg. \(<x_1,\dots,x_k>\).

• 节点分支的约束条件：eg. \(x_{k+1}\in [n]-\{x_1,\dots,x_k\}\).

• 代价函数：\(f(x_1,\dots,x_k)\).

• 界：一个 bound，eg. 目前已经检索到的最优解.

均摊分析

• 势能法
• 聚集法

线性规划

• 见线性规划章