一道初赛题
已知参数kkk,对于递推式T(n)=knT(n)+nT(n)=k \sqrt{n} T(\sqrt{n})+nT(n)=knT(n)+n的说法,正确的是()。
A.k=1A.k=1A.k=1时,T(n)=Θ(nlogn)T(n)= \Theta (n \log n)T(n)=Θ(nlogn)
B.k=1B.k=1B.k=1时,T(n)=Θ(nlog2n)T(n)= \Theta (n \log_2 n)T(n)=Θ(nlog2n)
C.k=4C.k=4C.k=4时,T(n)=Θ(nlogn)T(n)= \Theta (n \log n)T(n)=Θ(nlogn)
D.k=4D.k=4D.k=4时,T(n)=Θ(nlog2n)T(n)= \Theta (n \log_2 n)T(n)=Θ(nlog2n)
答案是D