主定理（一般式）
主定理（Master Theorem）是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系，通常采用分治策略解决问题的情况。
目录
主定理简化版的局限
主定理简化版的三种情况：
- I F IF IF f ( n ) = O ( n l o g b ( a − ε ) ) f(n) = O(n^ {log_b(a - ε)}) f(n)=O(nlogb(a−ε))，and ε > 0 ε > 0 ε>0，Then T ( n ) = Θ ( n l o g b ( a ) ) T(n) = Θ(n^{log_b(a)}) T(n)=Θ(nlogb(a))
- I F IF IF f ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) = Θ(n^{log_b(a)} ·log^k n) f(n)=Θ(nlogb(a)⋅logkn)，and k ≥ 0 k ≥ 0 k≥0，Then T ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k + 1 n ) T(n) = Θ(n^{log_b(a)} · log^{k+1} n) T(n)=Θ(nlogb(a)⋅logk+1n)
- I F IF IF f ( n ) = Ω ( n l o g b ( a + ε ) ) f(n) = Ω(n^{log_b(a + ε)}) f(n)=Ω(nlogb(a+ε))，and ε > 0 ε > 0 ε>0， a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn)≤c⋅f(n) 对于某个常数 c < 1 c < 1 c<1 和所有足够大的 n n n 成立，Then T ( n ) = Θ ( f ( n ) ) T(n) = Θ(f(n)) T(n)=Θ(f(n))
简化形式具有一定的限制条件，比如形式上必须是： T ( n ) = a ⋅ T ( n b ) + f ( n ) T(n)=a·T(\frac{n}{b})+f(n) T(n)=a⋅T(bn)+f(n)
并且 f ( n ) = n c f(n) = n^{c} f(n)=nc
三个反例：
- 子问题数量不是常数
T ( n ) = n ⋅ T ( n 2 ) + n 2 T(n)=n \cdot T(\frac{n}{2})+n^{2} T(n)=n⋅T(2n)+n2
- 子问题数量小于1
T ( n ) = 1 2 T ( n 2 ) + n 2 T(n)=\frac{1}{2}T(\frac{n}{2})+n^{2} T(n)=21T(2n)+n2
- 分解问题和合并解的时间不是 n c n^{c} nc
T ( n ) = 2 T ( n 2 ) + n l o g n T(n)=2T(\frac{n}{2})+nlogn T(n)=2T(2n)+nlogn
主定理一般形式
T ( n ) = a ⋅ T ( n b ) + f ( n ) , a > 0 , b > 1 T(n)=a·T(\frac{n}{b})+f(n),a>0,b>1 T(n)=a⋅T(bn)+f(n),a>0,b>1
- I F IF IF ∃ ε > 0 \exists ε > 0 ∃ε>0 使得 f ( n ) = O ( n l o g b ( a − ε ) ) f(n) = O(n^ {log_b(a - ε)}) f(n)=O(nlogb(a−ε)) ，Then T ( n ) = Θ ( n l o g b ( a ) ) T(n) = Θ(n^{log_b(a)}) T(n)=Θ(nlogb(a))
- I F IF IF ∃ k ≥ 0 \exists k ≥ 0 ∃k≥0 使得 f ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k n ) f(n) = Θ(n^{log_b(a)} ·log^k n) f(n)=Θ(nlogb(a)⋅logkn)，Then T ( n ) = Θ ( n l o g b ( a ) ⋅ l o g k + 1 n ) T(n) = Θ(n^{log_b(a)} · log^{k+1} n) T(n)=Θ(nlogb(a)⋅logk+1n)
- I F IF IF ∃ ε > 0 \exists ε > 0 ∃ε>0 使得 f ( n ) = Ω ( n l o g b ( a + ε ) ) f(n) = Ω(n^{log_b(a + ε)}) f(n)=Ω(nlogb(a+ε))，
且对于某个常数 c < 1 c < 1 c<1 和所有足够大的 n n n 有 a ⋅ f ( n b ) ≤ c ⋅ f ( n ) a · f(\frac{n}{b}) ≤ c · f(n) a⋅f(bn)≤c⋅f(n) ，Then T ( n ) = Θ ( f ( n ) ) T(n) = Θ(f(n)) T(n)=Θ(f(n))
主要考虑 函数 n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 的增长率关系
情况1： n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的快
T ( n ) = 9 T ( n 3 ) + n T(n)=9T(\frac{n}{3})+n T(n)=9T(3n)+n
- n l o g b a = n 2 n^{log_{b}{a}}=n^{2} nlogba=n2,
- f ( n ) = n = O ( n 2 − ϵ ) , ϵ ≤ 1 f(n)=n=O(n^{2-\epsilon }),\epsilon \le1 f(n)=n=O(n2−ϵ),ϵ≤1
- ⇒ T ( n ) = O ( n 2 ) \Rightarrow T(n)=O(n^{2}) ⇒T(n)=O(n2)
情况2： n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 增长率类似
T ( n ) = T ( 2 n 3 ) + 1 T(n)=T(\frac{2n}{3})+1 T(n)=T(32n)+1
- n l o g b a = n l o g 3 / 2 1 = n 0 = 1 n^{log_{b}{a}}=n^{log_{3/2}1}=n^{0}=1 nlogba=nlog3/21=n0=1,
- f ( n ) = 1 = Θ ( n l o g b a l o g 0 n ) f(n)=1=Θ(n^{log_{b}{a}}log^{0}n) f(n)=1=Θ(nlogbalog0n)
- ⇒ T ( n ) = O ( l o g n ) \Rightarrow T(n)=O(log n) ⇒T(n)=O(logn)
情况3： n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的慢
- f ( n ) f(n) f(n)比 n l o g b a n^{log_{b}{a}} nlogba 增长的更快，至少要快 Θ ( n ϵ ) Θ(n^{\epsilon}) Θ(nϵ) 倍，且 a f ( n b ) ≤ c f ( n ) af(\frac{n}{b}) \le cf(n) af(bn)≤cf(n)
T ( n ) = 3 T ( n 4 ) + n l o g n T(n)=3T(\frac{n}{4})+nlogn T(n)=3T(4n)+nlogn
- n l o g b a = n l o g 4 3 = n 0.793 n^{log_{b}{a}}=n^{log_{4}3=n^{0.793}} nlogba=nlog43=n0.793,
- f ( n ) = n l o g n = Ω ( n l o g 4 3 + ϵ ) , ϵ ≤ 0.207 f(n)=nlogn=Ω(n^{log_{4}3+\epsilon }),\epsilon \le0.207 f(n)=nlogn=Ω(nlog43+ϵ),ϵ≤0.207
- a f ( n b ) = 3 ( n 4 ) l o g ( n 4 ) ≤ 3 4 n l o g n = c f ( n ) , c = 3 4 af(\frac{n}{b})=3(\frac{n}{4})log(\frac{n}{4}) \le \frac{3}{4}nlogn=cf(n),c=\frac{3}{4} af(bn)=3(4n)log(4n)≤43nlogn=cf(n),c=43
- ⇒ T ( n ) = O ( n l o g n ) \Rightarrow T(n)=O(nlogn) ⇒T(n)=O(nlogn)
主定理不适用的情况
- n l o g b a n^{log_{b}{a}} nlogba 与 f ( n ) f(n) f(n) 的增长率不可比
- n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的快，但没有快 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍
- n l o g b a n^{log_{b}{a}} nlogba 比 f ( n ) f(n) f(n) 增长的慢，但没有慢 O ( n ϵ ) O(n^{\epsilon}) O(nϵ) 倍