3

この for ループの複雑さを理解するのに苦労しています

for (i = 4; i < n; i++)
{
    for (j = i - 3, sum = a[i - 4]; j <= i; j++)
    {
        sum += a[j];
    }
    System.out.println("sum thru" + i + ": " + sum);
}

入れ子になったループなので、この入れ子になったループの複雑さは n^2 だと思っていましたが、これは正しくなく、入れ子になったループは常に 2 次複雑であるとは限らないと誰かが言いました。

複雑さを良い方法で取得する方法がよくわかりません。Big-O と複雑さに関する記事をたくさん見てきましたが、それらは私がすべてを知っていることを期待していたので役に立ちませんでした。

私は答えを求めているのではなく、方法を求めています。このトピックのすべてに有効な式または方法はありますか? 割り当て数を取得する方法を知りたいのですが、残念ながらこれを行う方法がわかりません。

誰かが私にそれを段階的に説明できますか?

4

2 に答える 2

0

アルゴリズムの時間の複雑さに関するすべての問題を解決できる公式はないと思います。私にとって、Big-O を把握する最善の方法は、外側のプロセスから内側のプロセスへと段階的に進むことです。あなたや私のような初心者の標準的な方法でもあると思います。あなたの質問については、まず、外側のループは O(n) です。これは簡単です。次に、各ループ内に、別のループである内部プロセスがあります。そのループは i-3 から i、つまり O(1) になります。次に、そのプロセス内では、通常の割り当てステートメントであり、これも O(1) です。すべてをまとめると、big-O は O(n) * O(1) * O(1) = O(n) になります

于 2013-09-20T01:44:23.443 に答える