Master定理

Master定理

在演算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。

定理内容

假设有递归关系式$T(n)=aT(\frac{n}{b})+f(n)$，其中$a{\geq}1,b>1$，其中$n$为问题规模，$a$为递归的子问题数量，$\frac{n}{b}$为每个子问题的规模(假设每个子问题的规模基本一样)，$f(n)$为递归以外进行的计算工作。

• 如果存在常数$\epsilon>0$，有$f(n)=O(n^{\log_b^a-\epsilon})$，则$T(n)=\Theta(n^{\log_b^a})$.
• 如果存在常数$\epsilon{\geq}0$，有$f(n)=O(n^{\log_b^a}\log^{\epsilon}n)$，则$T(n)=\Theta(n^{\log_b^a}\log^{\epsilon+1}n)$.
• 如果存在常数$\epsilon>0$，有$f(n)=O(n^{\log_b^a+\epsilon})$，同时存在常数$c<1$以及充分大的$n$，满足$af(\frac{n}{b}){\leq}cf(n)$，则$T(n)=\Theta(f(n))$.

to be continued

计算斐波纳契数，分析算法复杂度.

参考文献

• 主定理 Master Theorem
• 主定理
• 算法的复杂度与 Master 定理
• 计算斐波纳契数，分析算法复杂度