当前位置: 首页 > 模式/算法 > 学习算法导论的经历(1)

学习算法导论的经历(1)

今天开始学习算法导论

主要的收获是学会了递归算法的时间复杂度的计算

T(n)=aT(n/b)+f(n)   a>=1和b>1是常数,f(n)是渐进正函数。

通过使用主方法,我们记住三种解法,可以很容易的解决很多递归式的时间复杂度。

对于T(n)我们有以下三种情况:

(1):若对于某个常数ε>0有f(n)=O(n^(log(b^(a-ε)))),则T(n)=Θ(n^(log(b^a))).

(2):若f(n)=Θ(n^(log(b^a))),则T(n)=Θ(n^log(b^a)lgn).

(3):若对某个常数ε>0有f(n)=Ω(n^logb^(a+ε)),且对于某个常数c<1和所有足够大的n有af(n/b)<=cf(n),则T(n)=Θ(f(n)).

文章来源于网络

转载时请以 超链接的形式 注明:转自疯狂泰克