Monthly Archives: April 2014

算法复杂度计算公式

主定理(Master Theorem) 设\(a \ge 1,b > 1\)为常数,f(n)是函数,T(n)为非负整数,且\(T(n) = aT(n/b) + f(n)\),则有以下结果: (1)若\(f(n) = O({n^{{{\log }_b}(a - \varepsilon )}}),\varepsilon > 0\),那么\(T(n) = \Theta ({n^{{{\log }_b}a}})\); (2)若\(f(n) = O({n^{{{\log }_b}a}})\),那么有\(T(n) = \Theta ({n^{{{\log }_b}a}}logn)\); (3)若\(f(n) = \Omega ({n^{{{\log }_b}(a + \varepsilon )}}),\varepsilon

spacer