主页 / coding / 问题 / 76938510
Accepted
Лука
Asked: 2023-08-20 16:07:18 +0800 CST

在循环中调用自身的递归函数的时间复杂度

  • 772

给定函数

void function(n) 
{        
for (int i = n; i > 0; i = floor(i/2))
 {            
  function(floor(i/2));
 }               
}

我很难找到此类函数的时间复杂度。Chatgpt 说它是log(n)但我相信它必须更大。如何写递推方程或者解决这个问题的正确方法是什么？

recursion

1 个回答

  1. Best Answer

    那么递推关系显然是

     T(0) = 1
 T(1) = T(0) + 1
 T(2) = T(1) + T(0) + 1
 T(n) = T(n/2) + T(n/4) + ... + T(1) + T(0) + 1
        i=n      i=n/2          i=2    i=1   i=0

    那么这是什么T(n)？为了简单起见，我们只关注 2 的幂。然后

     T(0) = 1
 T(1) = 2
 T(2) = 4
 T(2^2) = 8
 T(2^3) = 16
 ....
 T(2^k) = 2^k * 2

    即T(n) = 2 * n。所以总体复杂度似乎是O(n)。

    • 1

相关问题