关于渐进时间复杂度题已知某一算法的时间复杂度上限函数满足递归关系T(n)=2(T/2)+n，那么该算法的渐进时间复杂度为（）A.O(log2^2n）B.O(n^2)C.O（n）D.O(nlog2n)讲得简单一点，我初学。

Question

关于渐进时间复杂度题
已知某一算法的时间复杂度上限函数满足递归关系T(n)=2(T/2)+n，那么该算法的渐进时间复杂度为（ ）
A.O(log2^2n）B.O(n^2) C.O（n） D.O(nlog2n)
讲得简单一点，我初学。

Answer 1

其实最简单的办法一个个验算就行了
对于D
T(n)=nlog2n
2(T/2)+n=2*n/2*logn+n=n(logn+1)=nlog2n (log是以2为底，所以logn+1=log2n)
T(n)=2(T/2)+n
所以D满足
对于A,B,C可以验算得到不是正确的解
一般来说只要T(n)-(2(T/2)+n)为一个常数的情况下都是正确的，所以O(nlogn)也可以是一个渐进复杂度
当然这种做法只适合选择题，复杂点的要用到组合数学的知识，太长就不说了...