简记主定理

标签：Case dn ba 定理 简记 Theta log

狗都不学主定理

对于\(f(n)\)不带log的
形如

\[T(n) = aT(\frac{n}{b})+f(n) \]

• Case 1
  如果 $ f(n)=O(n^{\log_b a-\epsilon}) $，也就是 \(f(n)\)渐进意义上小于 \(n^{\log_ba}\)

\[ T(n)=\Theta(n^{\log_{b}{a}}) \]

• Case 2
  如果 $ f(n)=\Omega(n^{\log_b a+\epsilon}) $，也就是 \(f(n)\)渐进意义上大于 \(n^{\log_ba}\)

\[ T(n)=\Theta(f(n)) \]

• Case 1
  如果 $ f(n)=\Theta(n^{\log_ba}) $，也就是 \(f(n)\)与\(n^{log_ba}\)同阶

\[ T(n)=\Theta(n^{\log_{b}{a}} \log n) \]

对于带log的基本相同
形如

\[T(n)=aT(\frac{n}{b})+n^c\log^dn \]

• Case 1
  如果\(c<log_ba\)

\[T(n)=n^{log_ba} \]

• Case 2
  如果\(c=log_ba\)

\[T(n)=n^c\log^{d+1}n \]

• Case 3
  如果\(c>log_ba\)

\[T(n)=n^c\log^dn \]

本质上可行且更简单的方法是直接猜一个复杂度然后把两边的T都代进去看看是不是相等

标签：Case,dn,ba,定理,简记,Theta,log
From： https://www.cnblogs.com/Delov/p/16704174.html