【墨鳌】【Master Method】
Master Method
- 分治递归，是我们常用的程序设计思想，如何衡量一个递归算法设计的好坏呢？
- 这就使得我们得去思考：递归算法的复杂度如何计算
Master Method 是这样描述的：
\[T(n)=k(n/m)+f(n),f(n)=n^d \]\[T(n)\in \begin{cases} O(n^d) & k递归树
graph TD root("f(n)") son1("f(n/m)") son2("......") son3("f(n/m)") leaf1("f(n/m^i)") leaf2("f(n/m^i)") leaf3("f(n/m^i)") leaf4("f(n/m^i)") leaf5("f(n/m^i)") leaf6("f(n/m^i)") leaf7("f(n/m^i)") leaf8("f(n/m^i)") leaf9("f(n/m^i)") root-->son1 root-->son2 root-->son3 son1-...->leaf1 son1-...->leaf2 son1-...->leaf3 son2-...->leaf4 son2-...->leaf5 son2-...->leaf6 son3-...->leaf7 son3-...->leaf8 son3-...->leaf9-
第一层：\(1\) 个
-
第二层：\(k\) 个
-
第三层：\(k^2\) 个
-
第 \(i+1\) 层：\(k^i\)个
考虑叶子节点 \(f(n/m^i)=1\Longrightarrow n=m^i\iff i=\log_m{n}\)
推导过程
\[\because f(n)=n^d,\ i=\log_m{n}\\ \therefore T(n)=\Sigma f = f(n)+[k\cdot f(n/m)]+[k^2\cdot f(n/m^2)]+\dots+[k^i\cdot f(n/m^i)] \\ ? = (n^d)[1+\frac{k}{m^d}+(\frac{k}{m^d})^2+\dots+(\frac{k}{m^d})^i] \\ \]中括号内，为等比数列求和，公比 \(q\) 分类讨论
\[S=1+\frac{k}{m^d}+{(\frac{k}{m^d})}^2+...+{(\frac{k}{m^d})}^i, \qquad q=\frac{k}{m^d} \]考虑 \(i\rightarrow+\infty\)
-
when $ q=1,\ S=i+1=i$
-
when \(q<1,\ S=\frac{1}{1-q}\)
-
when \(q>1,\ S=q^i\)
$ \therefore T(n)=n^d\cdot S$ 分三类讨论：
- \(q=1\iff k=m^d\qquad T(n)=n^d\cdot i=n^d\cdot \log_m{n}=O(n^d\cdot \log_m{n})\)
- \(q<1\iff k
- \(q>1\iff k>m^d\qquad T(n)=n^d\cdot q^i=n^d\cdot (\frac{k}{m^d})^{(\log_m{n})}=O(n^{\log_m{k}})\qquad (*)\)
\((*)\) 推导：
\(n^d\cdot (\frac{k}{m^d})^{(\log_{\text{m}}{n})}\)
\(=n^d\cdot \frac{k^{\log_{\ \text{ m}}{n}}}{(m^d)^{\log_{\ \text{ m}}{n}}}\)
\(=n^d\cdot \frac{k^{\log_{\ \text{ m}}{n}}}{(m^{\log_{\ \text{ m}}{n}})^d}\)
\(=n^d\cdot \frac{k^{\log_{\ \text{ m}}{n}}}{n^d}\)
\(=k^{\log_{\ \text{m}}{n}}\)
\(=k^{\frac{\log_{\ \text{ k}}{n}}{\log_{\ \text{ k}}{m}}}\)
\(=(k^{\log_{k}{n}})^\frac{1}{log_{\ k}{\ m}}\)
\(=n^{\log_{m}{k}}\)
练习题
master method
\[T(n)\in \begin{cases} O(n^d) & k$ 1.\quad T(n)=T(n/3)+n$
\[k=1,m=3,d=1\Longrightarrow k$ 2.\quad T(n)=T(2n/3)+1$
\[k=1,m=3/2,n=0\Longrightarrow k=m^d\\ T(n)=O(n^dlog_m{n})=\Theta(\log{n}) \]$ 3.\quad T(n)=4T(n/2)+n$
\[k=4,m=2,d=1\Longrightarrow k>m^d\\ T(n)=O(n^{\log_m{k}})=\Theta(n^2) \]$ 4.\quad T(n)=2T(n/2)+n$
\[k=2,m=2,n=1\Longrightarrow k=m^d\\ T(n)=O(n^dlog_m{n})=\Theta(n\log{n}) \]