T(n)=aT(bn)+f(n) 和 nlogba 比较,哪个大取哪个,一样大就乘个 logn 下面对 f 函数的重要性进行讨论 如果存在某个常数 ϵ>0 有 f(n)=O(nlogba−ϵ) 则 T(n)=Θ(nlogba) 若 f(n)=Θ(nlogba) T(n)=Θ(nlogbalgn) 若某个常数 ϵ>0 有 f(n)=Ω(nlogba+ϵ) 且对常数 c<1,与所有足够大的 n 有 af(bn)≤cf(n) 则 T(n)=Θ(f(n))