浏览量:850

算法复杂度计算公式

主定理(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 > 0\),且对于某个常数c和所有充分大的n,有\(af(n/b) \le cf(n)\),那么\(T(n) = \Theta (f(n)),c < 1\)

 

 

spacer

Leave a reply