关于这道题
按照主定理,f(n)=O(nlogn)=O(nlogba+ϵ)=O(n1+ϵ)f(n) = O(nlogn) = O(n^{log_ba + \epsilon}) = O(n^{1 + \epsilon})f(n)=O(nlogn)=O(nlogba+ϵ)=O(n1+ϵ) ,符合主定理的第三种形式,那应该 T(n)=f(n)=O(nlogn)T(n) = f(n) = O(nlogn)T(n)=f(n)=O(nlogn) 。但是答案显然是 O(nlog2n)O(nlog^2n)O(nlog2n) 。
线上询问了老师,老师说这是因为这里 f(n) 不是关于 n 的多项式。但是我不是很理解(因为例如归并的f(n)=n也可以求解),所以想询问一下主定理能够在哪些条件下满足,以及一般该如何解决这道题。