複数の関数呼び出しを持つ再帰関数の大きなO？

Question

私はこの再帰関数の最悪のケースの時間計算量を決定する問題を抱えている：

long f(int n) { 
    if(n <= 0) return 1; 
    else { 
    return f(n/2) + f(n/2) + f(n/2); 
    } 
} 

私はあなたが一度だけF（N/2）を返すれた場合、それはO（n個のログを記録）になることを理解しています。だから私は3つ、4つ、5つ、などの時間は、関数の大きなOに影響を与えるだろうかと思っていたおかげで！

Answer 1

定数で乗算すると、は決してになります。もちろん、実行時間は約3倍になりますが、問題はnの値に対して時間がどのように増加するかということであり、クロックの内容とは異なります。

同じ値を持つ同じ関数を呼び出しているので、これは簡単に当てはまります。あなたは3つの異なるコール、など

return f(n/2) + f(int(sqrt(n)) + f(n-1) 

を持っていた場合、これを確実に

return 3 * f(n/2) 

置き換えることができる...あなたは、各の複雑さを計算し、唯一の最も考慮する必要があるだろう複合体。それはこの機能では難しくありません。ただし、Collat​​zシーケンスなどのより複雑な関数では、2次および3次のすべての複雑さを考慮すると、より困難な時間があります。 あなたの質問は簡単ですが、フォローアップの質問には注意してください：あなたはまた、間接的に再帰関数を呼び出して、多くの問題、など

long f(int n); 

long g(int n) { 
    if(n <= 2) return 1; 
    else { 
    return f(n*n mod 10) + g(n-2); 
    } 
} 

long f(int n) { 
    if(n <= 0) return 1; 
    else { 
    return f(n/2) + g(n/2); 
    } 
} 

ボトムラインを持っているでしょう。