algorithm - アルゴリズムの時間計算量

Question

これは、与えられた関数の時間計算量を計算しなければならない問題です

f(i) = 2*f(i+1) + 3*f(i+2)
For (int i=0; i < n; i++)
F[i] = 2*f[i+1] 

私が思うに、このアルゴリズムの複雑さは O(2^n) + O(n) であり、最終的には O(2^n) です。私が間違っている場合は修正してください。

Answer 1

まず、今後これらを解決するために必要なすべての情報がここにあります。

あなたの質問に答えるために。I 自体に関して f(i) の定義を提供していないため、上記の内容から実際の複雑さを判断することは不可能です。ただし、一般的に for ループのような

for (i = 0; i < N; i++) {
    sequence of statements
}

は N 回実行されるため、一連のステートメントも N 回実行されます。ステートメントが O(1) であると仮定すると、for ループの合計時間は N * O(1)、つまり全体で O(N) になります。上記のあなたの場合、自由に書き直すと

f(0) = 0;
f(1) = 1;
f(i+2) = 2*f(i+1) + 3*f(i)
for (int i=0; i < n; i++)
    f[i] = 2*f[i+2] 

次に、明確に定義された一連の操作があり、n 操作の複雑さは、上記の例のように、n * O(1)、つまり O(n) であることは明らかです。

これが役立つことを願っています。