汽车行业工程师 发表于 2020-10-28 23:32:01

求解时间复杂度！！！

   

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



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

2269099035 发表于 2020-10-28 23:53:38

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为底

网上找的。
页: [1]
查看完整版本: 求解时间复杂度！！！