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

Question

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

我很难发现此类函数的复杂性。 Chatgpt 说它是 log(n) 但我相信它必须更大。如何编写递归方程或解决此问题的正确方法是什么。

Answer 1

那么，递推关系显然是

 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)。