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

Question

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

在查找大 O 表示法时遇到问题，网络上此类示例不多......

const fun = (n) => {
    if (n === 0) {
        return;
    }
    console.log(n);
    for (let i = 0; i < n; i++) {
        fun(n - 1);
    }
};

Answer 1

第一个函数是对数的，也就是说，它要执行的步骤数将与输入为 ~n 的对数相关，因此它是 O(log(n))

var counter = 0;
function f(n) 
{    
counter++;
for (i = n; i > 0; i = parseInt(i / 2))
 {            
  f(parseInt(i/2));
 }               
}
for (let i = 1; i <= 4096; i *= 2) {
    counter = 0;
    f(i);
    console.log(i + ': ' + counter);
}

第二个函数循环 n 个数字，每个数字循环 i - 1 个数字，所以它的复杂度为

1 + 2 + 3 + ... + n = n * (n + 1) / 2，即复杂度为 O(n^2)