2023-08-22 11:42:47 顶置3

前言

推了半个小时的式子，我感觉我已经彻底的理解了，所以前来写一篇复杂度 $master$ 公式计算的结论和证明。

$master$ 公式

可以解决的问题——给出递归的复杂度公式：

\[\large\begin{cases} T(1)=1\\T(n)=aT(\frac{n}{b})+f(n)\\f(n)=n^d\end{cases} \]

求递归 $T(n)$ 的复杂度。

结论：

\[\large T(n)=\begin{cases} O(n^d\log _bn)&\log _b a=d\\O(n^d)&\log _ba<d\\O(n^{\log _ba})&\log _ba>d\end{cases} \]

证明：

\[\large\begin{aligned}T(n)&=aT(\frac{n}{b})+f(n)\\&=a(aT(\frac{n}{b^2})+(\frac{n}{b})^d)+n^d\\&=a^2T(\frac{n}{b^2})+n^d(1+\frac{a}{b^d})\end{aligned} \]

用相同的方法将 $T(n)$ 展开 $m$ 次，可得：

\[\large\begin{aligned}T(n)&=a^mT(\frac{n}{b^m})+n^d(1+\frac{a}{b^d}+(\frac{a}{b^d})^2+\dots+(\frac{a}{b^d})^{m-1})\end{aligned} \]

展开到最后，显然 $\frac{n}{b^m}$ 可以取到 $1$，那么 $m=\log _bn$。

那么：

\[\large T(n)=a^{\log _bn}T(1)+n^d(1+\frac{a}{b^d}+(\frac{a}{b^d})^2+\dots+(\frac{a}{b^d})^{-1+\log _bn}) \]

当 $\frac{a}{b^d}=1$ 时，此时 $a=b^d$,$d=log_ba$,代入可得:

\[\large \begin{aligned}T(n)&=a^{\log _bn}+n^{\log _ba}log_bn\\&=n^{\log _ba}+n^{\log _ba}log_bn\\&=n^d(1+\log _bn)\end{aligned} \]

去掉常数项可得当 $\frac{a}{b^d}=1$ 时，$T(n)=n^d\log _bn $。

当 $\frac{a}{b^d}\ne1$ 时，我们令 $S=1+\frac{a}{b^d}+(\frac{a}{b^d})^2+\dots+(\frac{a}{b^d})^{-1+\log_b n}$。

\[\large S=1+\frac{a}{b^d}+(\frac{a}{b^d})^2+\dots+(\frac{a}{b^d})^{-1+\log_b n} \]

\[\large \frac{a}{b^d}S=\frac{a}{b^d}+(\frac{a}{b^d})^2+\dots+(\frac{a}{b^d})^{\log_b n} \]

\[\large (\frac{a}{b^d}-1)S=(\frac{a}{b^d})^{\log _bn}-1 \]

\[\large S=\frac{(\frac{a}{b^d})^{\log _bn}-1}{\frac{a}{b^d}-1} \]

\[\large \begin{aligned}T(n)&=a^{\log _bn}+n^d\frac{(\frac{a}{b^d})^{\log _bn}-1}{\frac{a}{b^d}-1}\\&=n^{\log _ba}+\frac{n^{\log _ba}-n^d}{\frac{a}{b^d}-1}\\&=\frac{\frac{a}{b^d}n^{\log _ba}-n^d}{\frac{a}{b^d}-1}\end{aligned} \]

当 $\frac{a}{b^d}<1\iff \log _ba<d$ 时，显然 $n^d>\frac{a}{b^d}n^{\log _ba}$，所以近似看作 $T(n)=n^d=f(n)$，否则 $T(n)=n^{\log _ba}$。