[Note] 分治策略

分治思维

1. 生态位

• 分治 把一个复杂的问题细分成若干结构相同但规模更小的子问题，然后将每个子问题的解合并起来，就得到了复杂问题的解。

• 地位：分解问题的一种思维方式。

• 识别：

  1. 可以把原问题划分为多个无关的子问题，这里的划分一般都是人为给定的。

  2. 子问题的答案可以高效合并，也就是知道了子问题的答案可以高效计算其对全局的答案会产生什么影响。

  3. 当前问题的答案可以高效求出，在这里 “高效” 的复杂度一般为 $O(n)$ 或 $O(n \log n)$，也就是线性扫一遍或者排个序的复杂度差不多。

2. 逻辑支点

• 核心原理：分而治之

• 由于子问题和原问题类型相同，时间复杂度经常可以写成形如 $T(n) = aT( \frac{n}{b} ) + f(n)$ 的递归式，在 $n = O(1)$ 时 $T(n) = O(1)$ 边界。

• 主定理：

  1. $f(n) = O(n^{\log_{b}a} \log^cn)$ 时 $T(n) = O(n^{\log_{b}a} \log^{c+1}n)$
  2. $f(n) = O(n^{-\epsilon + \log_{b}a}), \epsilon > 0$ 时 $T(n) = O(n^{\log_{b}a})$
  3. $f(n) = O(n^{c_{1}}\log^{c_{2}}n), c_{1} ? \log_{b}a$ 时 $T(n) = O(n^{c_{1}} \log^{c_{2}}n)$

这部分内容仅供参考，不要求掌握。