算法|算法分析（复发）|问题8-yiteyi-C++库

以下递归函数的时间复杂度是多少：

null

                     int                               DoSomething (                               int                               n)                   
                     {                   
                                         if                               (n <= 2)                   
                                         return                               1;                   
                                         else                   
                                         return                               (DoSomething (                               floor                               (                               sqrt                               (n))) + n);                   
                     }                   

（A） $heta$ （n）（B） $heta$ （nlogn）（C） $heta$ （logn）（D） $heta$ （logn） （A） A. （B） B （C） C （D） D 答复: （D） 说明： DoSomething（）的递归关系为

  T(n) =  T() + C1 if n > 2

我们忽略了地板的部分，因为它是地板还是天花板都无关紧要。

  Let n = 2^m,  T(n) = T(2^m)
  Let T(2^m) =  S(m)

  From the above two, T(n) = S(m)

  S(m) = S(m/2) + C1  /* This is simply binary search recursion*/
  S(m)  = O(logm)      
          = O(loglogn)  /* Since n = 2^m */
  
  Now, let us go back to the original recursive function T(n) 
  T(n)  = S(m) 
          = O(LogLogn)

这个问题的小测验

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章