【初赛】主定理(时间复杂度)

有错误欢迎指出

主定理:

对于\(T(n)=aT(\dfrac{n}{b})+f(n),T(1)=O(1)\),有:

  1. \(f(n)=O(n^{\log_ba-\epsilon})\),\(\epsilon>0\)时,\(T(n)=\Theta(n^{\log_b a})\)
  2. \(f(n)=\Theta(n^{\log_ba}\log_b^l n)\)时,\(T(n)=\Theta(n^{\log_b a}\log_b^{l+1} n)\)
  3. \(f(n)=\Omega(n^{\log_ba+\epsilon})\),\(\epsilon>0\)且有一实数\(c\)满足\(0<c<1,af(\dfrac{n}{b})\leq cf(n)\)时,\(T(n)=\Theta(f(n))\)

递推式转化和式

对于\(T(n)=aT(\dfrac{n}{b})+f(n),T(1)=O(1)\)的式子,我们假设\(n=b^k,k\)为正整数,则有:

\(T(n)=aT(\dfrac{n}{b})+f(n)\)

\(=a(aT(\dfrac{n}{b^2})+f(\dfrac{n}{b}))+f(n)\)

\(=a^2T(\dfrac{n}{b^2})+af(\dfrac{n}{b})+f(n)\)

\(=a^3T(\dfrac{n}{b^3})+a^2f(\dfrac{n}{b^2})+af(\dfrac{n}{b})+f(n)\)

\(=a^k\times T(1)+\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

\(=a^{\log_b n}+\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

\(=n^{\log_b a}+\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

上一步是由\(a^{\log_bc}=(b^{\log_ba})^{\log_bc}=b^{\log_ba\times\log_bc}=(b^{\log_bc})^{\log_ba}=c^{\log_ba}\)得到的。

接下来研究\(T(n)-n^{\log_b a}\)即可,不妨设其为\(t(n)\)

情况1 \(f(n)=O(n^{\log_ba-\epsilon})\),\(\epsilon>0\)

\(t(n)=\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

\(=\sum\limits_{j=0}^{k-1}a^j(\dfrac{n}{b^j})^{\log_b a-\epsilon}\)

\(=n^{\log_b a-\epsilon}\sum\limits_{j=0}^{k-1}\dfrac{a^j}{b^{j(\log_b a-\epsilon)}}\)

\(=n^{\log_b a-\epsilon}\sum\limits_{j=0}^{k-1}\dfrac{a^jb^{j\epsilon}}{b^{j\log_b a}}\)

\(=n^{\log_b a-\epsilon}\sum\limits_{j=0}^{k-1}b^{j\epsilon}\)

\(=n^{\log_b a-\epsilon}(\dfrac{(b^\epsilon)^{k}-1}{(b^\epsilon)-1})\)

\(=n^{\log_b a-\epsilon}(\dfrac{n^{\epsilon}-1}{(b^\epsilon)-1})\)

\(=\dfrac{n^{\log_b a}-n^{\log_b a-\epsilon}}{(b^\epsilon)-1}\)

所以\(t(n)=\Theta(n^{\log_b a})\),所以\(T(n)=\Theta(n^{\log_b a})\)

情况2 \(f(n)=\Theta(n^{\log_ba}\log_b^l n)\)

\(t(n)=\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

\(=\sum\limits_{j=0}^{k-1}a^j(\dfrac{n}{b^j})^{\log_b a}\log_b^l\dfrac{n}{b^j}\)

\(=n^{\log_b a}\sum\limits_{j=0}^{k-1}\dfrac{a^j}{b^{j\log_b a}}\log_b^l\dfrac{n}{b^j}\)

\(=n^{\log_b a}\sum\limits_{j=0}^{k-1}(k-j)^l\)

\(\leq n^{\log_b a}k^{l+1}\)

\(=n^{\log_b a}\log_b^{l+1} n\)

所以\(T(n)=\Theta(n^{\log_b a}\log_b^{l+1} n)\)

情况3 \(f(n)=\Omega(n^{\log_ba+\epsilon})\),\(\epsilon>0\)且有一实数\(c\)满足\(0<c<1,af(\dfrac{n}{b})\leq cf(n)\)

\(t(n)=\sum\limits_{j=0}^{k-1}a^jf(\dfrac{n}{b^j})\)

\(\leq \sum\limits_{j=0}^{k-1}c^jf(n)=f(n)\sum\limits_{j=0}^{k-1}c^j\)

\(\leq f(n)\sum\limits_{j=0}^{\infty}c^j\)

\(=\dfrac{f(n)}{1-c}\leq f(n)\)

所以\(t(n)=\Theta(f(n))\),且\(t(n)>O(n^{\log_b a})\),所以\(T(n)=\Theta(f(n))\)

【初赛】主定理(时间复杂度)

上一篇:react页面缓存 使用本地存储


下一篇:009.数据类型-实型