如何計算遞歸函數的時間複雜度？

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