主定理求解时间复杂度
ZhangChuan1350
·
·
算法·理论
形如 T(n)=aT(\dfrac nb)+f(n) 的递推式，且其递归条件一般为 T(1)=x。
其中 a 表示子问题分解数量，b 表示子问题缩小比例，aT(\dfrac nb) 表示求解子问题代价，f(n) 表示合并子问题代价，必须保证 a\geqslant1,b>1
对参数的要求：a、b 为常数；对于所有足够大的 n，f(n)>0。
则时间渐进复杂度（以下简称时间复杂度）可利用主定理 进行求解。
:::info[主定理公式]{open}
O(n^{\log_ba})&f(n)=O(n^{\log_ba-k})，\text{其中 }k>0\\
O(n^{\log_ba}\log^{k+1}n)&f(n)=O(n^{\log_ba}\log^kn)，\text{其中 }k\geqslant0\\
O(f(n))&f(n)=O(n^{\log_ba+k})\text{ 且 }af(\dfrac nb)\leqslant cf(n)，\text{其中 }k>0,c<1
\end{cases}
注：
:::
:::info[主定理详解]
|**主定理详解** |< |
|:----:|:----:|
|$\text{Case 1}$|当 $aT(\dfrac nb)$ **主导**，$k>0$ 保证 $f(n)$ **多项式意义上慢于** $n^{\log_ba}$，时间复杂度由 $\log_ba$ 决定。|
|$\text{Case 2}$|当 $aT(\dfrac nb)$ 与 $f(n)$ **同阶**，$k\geqslant0$ 保证 $f(n)$ 的增长率**至少**和 $n^{\log_ba}$ 一样快，**仅多一个单项式因子**。|
|$\text{Case 3}$|当 $f(n)$ **主导**，$k>0$ 保证 $f(n)$ **多项式意义上快于** $n^{\log_ba}$，时间复杂度由 $f(n)$ 决定。**正则条件**确保工作量**指数递减**。|
|如何选择情况|< |
|:----:|:-:|
|$\text{Case 1}$|当 $f(n)$ 的增长速度慢于 $n^{\log_ba}$。|
|$\text{Case 2}$|当 $f(n)$ 的增长速度和 $n^{\log_ba}$ 相差不多。|
|$\text{Case 3}$|当 $f(n)$ 的增长速度快于 $n^{\log_ba}$。|
**提示**：$\text{Case 2}$ 的递归数**高度**为 $\log n$，**每层工作量**为 $n^{\log_ba}\log^kn$，因此总工作量为两者相乘，即 $n^{\log_ba}\log^{k+1}n$。
:::
::::info[主定理的证明]
:::info[证明准备]
构建一个**递归树**
**根节点：** 工作量 $=f(n)
| 高度（根节点高度为 1）： h=\log_bn+1 |
高度 |
问题规模 |
节点数 |
该层每节点工作量 |
该层总工作量 |
| 1 |
n |
1 |
f(n) |
f(n) |
| 2 |
\dfrac nb |
a |
f(\dfrac nb) |
a\cdot f(\dfrac ab) |
| 3 |
\dfrac n{b^2} |
a^2 |
f(\dfrac n{b^2}) |
a^2\cdot f(\dfrac n{b^2}) |
| … … … … |
< |
< |
< |
< |
| h |
1 |
a^{h-1} |
O(1) |
O(a^{h-1}) |
总工作量公式:
T(n)=\sum_{i=1}^na^{i-1}f(\dfrac n{b^{i-1}})+O(a^{h-1})
由于 a^{h-1}=a^{\log_bn}=n^{\log_ba}
则可得
T(n)=\sum_{i=1}^{h-1}a^{i-1}f(\dfrac n{b^{i-1}})+O(n^{\log_ba})
令 j=i-1，则
T(n)=\sum_{j=0}^{h-2}a^jf(\dfrac n{b^j})+O(n^{\log_ba})
:::
:::info[\text{Case 1} 证明过程]
条件： 存在 k>0，使得 f(n)=O(n^{\log_ba-k})
证明：
第 j 层的工作量为
a^jf\left(\dfrac n{b^j}\right)\leqslant a^j\cdot c\cdot\left(\dfrac n{b^j}\right)^{\log_ba-k}
化简，得
a^jf\left(\dfrac n{b^j}\right)\leqslant c\cdot n^{\log_ba-k}\cdot b^{jk}
内部层工作量总和为
\sum_{j=0}^{h-2}a^jf\left(\dfrac n{b^j}\right)\leqslant c\cdot n^{\log_ba-k}\cdot\sum_{j=0}^{h-2}b^{jk}
因此
\sum_{j=0}^{h-2}a^jf\left(\dfrac n{b^j}\right)=O(n^kn^{\log_ba-k})=O(n^{\log_ba})
加上叶子层工作量 O(n^{\log_ba})，得
T(n)=O(n^{\log_ba})+O(n^{\log_ba})=O(n^{\log_ba})
综上： T(n)=O(n^{\log_ba})
:::
:::info[\text{Case 2} 证明过程]
条件： f(n)=O(n^{\log_ba}\log^kn)，\text{其中 }k\geqslant0
证明：
第 j 层的工作量为
a^jf\left(\dfrac n{b^j}\right)=O\left(a^j{\left(\dfrac n{b^j}\right)}^{\log_ba}\log^k\dfrac n{b^j}\right)
关键变换
a^j\left(\dfrac n{b^j}\right)^{\log_ba}=b^{j\log_ba}\cdot n^{\log_ba}\cdot b^{-j\log_ba}=n^{\log_ba}
因此
a^jf\left(\dfrac n{b^j}\right)=O\left(n^{\log_ba}\log^k\dfrac n{b^j}\right)
内部层工作量总和为
\sum_{j=0}^{h-2}a^jf\left(\dfrac n{b^j}\right)=O\left(n^{\log_ba}\sum_{j=0}^{h-2}\log^k\dfrac n{b^j}\right)
化简对数项，得
\log\dfrac n{b^j}=\log n-j\log b
令 m=\log n，则求和变为
\sum_{j=0}^{h-2}(m-j\log b)^k
由于 h-2=\log_bn-1，且 \log b 是常数，该求和为
O(m^{k+1})=O(\log^{k+1}n)
因此
\sum_{j=0}^{h-2}a^jf\left(\frac n{b^j}\right)=O\left(n^{\log_ba}\log^{k+1}n\right)
加上叶子层工作量 O(n^{\log_ba})，得
T(n)=O(n^{\log_ba}\log^{k+1}n)+O(n^{\log_ba})=O(n^{\log_ba}\log^{k+1}n)
综上： T(n)=O(n^{\log_ba}\log^{k+1}n)
:::
:::info[\text{Case 3} 证明过程]
条件： 存在 k>0,c<1，使得 f(n)=O(n^{\log_ba+k}) 且 af(\dfrac nb)\leqslant cf(n)
证明：
根据正则条件，得
af\left(\dfrac nb\right)\leqslant cf(n)\\
a^3f\left(\dfrac n{b^3}\right)\leqslant c\cdot af\left(\dfrac nb\right)\leqslant c^3f(n)\\.\\.\\.\\
a^jf\left(\dfrac n{b^j}\right)\leqslant c^jf(n)
内部层工作量总和为
\sum_{h-2}^{j=0}a^jf\left(\dfrac n{b^j}\right)\leqslant f(n)\sum_{j=0}^{h-2}c^j\leqslant f(n)\sum_{j=0}^{\infty}=\dfrac{f(n)}{1-c}=O(f(n))
现在证明下界： 由于 f(n)=O(n^{\log_ba+k}) ，且 k>0，有
f(n)\geqslant dn^{\log_ba+k}，\text{其中 }d>0
因为 n^{\log_ba}=O(n^{\log_ba+k})=O(f(n))，所以叶子层工作量为
O(n^{\log_ba})=O(f(n))
因此
T(n)=O(f(n))+O(f(n))=O(f(n))
下界证明： 显然 T(n)\geqslant f(n)，所以
T(n)=O(f(n))
综上：T(n)=O(f(n))
:::
::::
::::success[主定理的应用]
:::info[主定理的计算方法]
- 判断递推式是否符合主定理标准形式，并得出 a,b,f(n) 的值。
- 计算关键值（n^{\log_ba}）。
- 判断 f(n) 与 O(n^{\log_ba}) 的增长速度。
- 根据其增长差异选择条件。
- 得出最终时间复杂度。
:::
:::info[归并排序]
递推式 T(n)=2T(\dfrac n2)+O(n)，符合主定理标准形式。
可得出 a=2,b=2,f(n)=O(n)。
计算关键值：O(n^{\log_22})=O(n)。
比较 f(n) 和 O(n^{\log_ba})： f(n)=O(n) （满足 \text{Case 2}）。
选择 \text{Case 2}，k=0，得出 O(n^{\log_ba}\log^kn)=O(n)=f(n)。
因此 时间复杂度为 O(n^{\log_ba}\log^{k+1}n)=O(n\log n)。
:::
:::info[二分查找]
递推式 T(n)=T(\dfrac n2)+O(1)，符合主定理标准形式。
可得出 a=1,b=2,f(n)=O(1)。
计算关键值： O(n^{\log_21})=1。
比较 f(n) 和 O(n^{\log_ba})： f(n)=O(1) （满足 \text{Case 2}）。
选择 \text{Case 2}，k=0，得出 O(n^{\log_ba}\log^kn)=O(1)=f(n)。
因此 时间复杂度为 O(n^{\log_ba}\log^{k+1}n)=O(\log n)。
:::
:::info[Strassen 矩阵乘法]
递推式 T(n)=7T(\dfrac n2)+O(n^2)，符合主定理标准形式。
可得出 a=7,b=2,f(n)=O(n^2)。
计算关键值： O(n^{\log_27})。
比较 f(n) 和 O(n^{\log_ba})： f(n)>O(n^{\log_27}) （检查 \text{Case 1}）。
检查 取 k=\log_27-2，f(n)=O(n^{\log_ba-k})=O(n^2) （满足 \text{Case 1}）。
因此 时间复杂度为 O(n^{\log_ba})=O(n^{\log_27})\approx O(n^{2.807})。
:::
:::info[二叉树遍历]
递推式 T(n)=2T(\dfrac n2)+O(1)，符合主定理标准形式。
可得出 a=2,b=2,f(n)=O(1)。
计算关键值： O(n^{\log_22})=O(n)。
比较 f(n) 和 O(\log_ba)： f(n)<O(n) （检查 \text{Case 1}）。
检查 取 k=1，则 f(n)=O(n^{\log_22-1})=O(1) （满足 \text{Case 1}）。
因此 时间复杂度为 O(n^{\log_ba})=O(n)。
:::
::::
:::warning[主定理不适用的情况]
- 递推式形式不满足 T(n)=aT(\dfrac nb)+f(n)。
-
- 满足 \text{Case 3} 但不满足正则条件。
-
- 对于足够大的 n，f(n) 不一定大于 0。
- 对于 \text{Case 3}，f(n) 与 n^{\log_b a} 的增长差异非多项式级别。
:::