首页 > 其他分享 >主定理学习笔记

主定理学习笔记

时间:2022-11-30 10:24:30浏览次数:59  
标签:log epsilon 定理 笔记 学习 dfrac 此时 Theta

分析复杂度时可能有用。(主定理狗都不学)

若有递归式 \(T(n)=aT(\dfrac{n}{b})+f(n)\)

则分以下三种情况:

  • \(f(n)=O(n^{\log _ b a-\epsilon}),\epsilon>0\),此时 \(T(n)=\Theta(n^{\log_ b a})\)
  • \(f(n)=\Theta(n^{\log_ b a}\log^k n),k\geq 0\),此时 \(T(n)=\Theta(n^{\log_ b a}\log^{k+1} n)\)
  • \(f(n)=\Omega(n^{\log_b a+\epsilon}),\epsilon>0\),此时若 \(\exists c<1\) 使得 \(\forall n>n_0,af(\dfrac{n}{b})\leq cf(n)\),则 \(T(n)=\Theta(f(n))\)

标签:log,epsilon,定理,笔记,学习,dfrac,此时,Theta
From: https://www.cnblogs.com/pref-ctrl27/p/16937617.html

相关文章