再帰関数の時間複雑度を計算するには？

Question

次のコードの時間的複雑度はどのくらいですか？

私の推測：

ザ・ループのためには、すなわち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（ Nを記録）。最初のいくつかの呼び出しが行くループC.によって行われる作業の量を呼び出します

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

Cが表示された回数は、それが1になる前に、あなたは3でn個を分割できる回数になります正確にはログです nです。総仕事はC * log n、またはO（log N）です。