浏览量:1,030

算法复杂度计算公式

主定理(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