algorithm - 関数f（n）= f（n-1）+ f（n-2）+ f（n-3）+ ...+1の複雑さはどれくらいですか

Question

nについてこの関数を計算するための時間計算量はどれくらいですか。

int rec(int n)
{
    if (n<=1) {
        return n ;
    }
    int i;
    int sum=0;
    for (i=1; i<n; i++) {
       sum=sum+rec(i); 
    }
    return sum ;
}

Answer 1

さてこれを破りましょう

 (1)        f(n) = f(n-1) + f(n-2) + ... f(1) + 1

でも、

 (2)        f(n-1) = f(n-2) + ... f(1) + 1

したがって、（2）を（1）に接続すると

 (3)        f(n) = f(n-1) + f(n-1) = 2 f(n-1)

f（2）= 1であるため、これは明らかに2 ⁿです（詳細：この再発の複雑さを理解することはできません）。ええと、実際には2 ^{n-1ですが、大きなOでは、 -1}は/ 2と同じなので、それはまったく問題ではありません。