求解时间复杂度！！！

汽车行业工程师

   

T（n)=  if(n==1)
           {  T(n)=1;}
           if(n>1)
           {  2T(n/2)+n;}
n为问题的规模，设n为2的整数次幂



求大神讲解该题时间复杂度的过程，感谢了！

2269099035

T(n) = 2T(n/2) + O(n), 且假设n=2的k次方。
      T(n) = 2T(n/2) + O(n)
           = 2T(n/4) + 2O(n/2) + O(n)
           = ...
           = O(n) + O(n) + ... + O(n) + O(n) + O(n)
           = k * O(n)
           = O(k*n)
           = O(nlog2n) //以2为底

网上找的。