如何计算递归函数的时间复杂度？

Question

以下代码的时间复杂度是多少？

我的猜测：

的for循环固定时间运行，即3.与函数调用本身有N/3。所以'n'每次收缩3次，时间复杂度为O（log N）？

void function(int n){ 
    if(n == 1) 
     return 1; 
    for(int i = 0; i < 3; i++){ 
     cout << "Hello"; 
    } 
    function(n/3); 
} 

Answer 1

是的，这是为O（log N）。调用由循环C.所做的工作的前几个电话会去量：

f(n) = C + f(n/3) = C + C + f(n/9) = C + ... + C + f(1)

C出现的次数将是您可以通过3它到达前1整除n的次数，这正好是日志 n。因此总的工作量是C * log n或O（log N）。