软考递归式时间复杂度

该方法适用于特定格式的递归式

例如:

T(n)=4T(n/2)+n , 则a=4,b=2,f(n)=n,计算nlog(b,a)=n2>f(n), 满足模式一,因此T(n) = nlog(b,a)=O(n2)

T(n)=4T(n/2)+n2,则根据上面计算,满足模式二,因此T(n)=O(n2logn)

T(n)=4T(n/2)+n3,满足模式三,T(n)=O(n3)

发表评论

电子邮件地址不会被公开。 必填项已用*标注