-2

FOR ループ (n 回実行する必要がある) などのループの複雑さを計算する必要がある場合、FOR ループの条件が失敗して中断した場合の反復もカウントする必要がありますか?

次に例を示します。

iおよびnは正の整数です

for(i=0;i<n;i++)
{
   //some code. All are constant expressions and there are no break statements.
}

これで、内部コードは 0 から n-1 回 (n 回) 実行されます。i = n の場合、ループは中断しますが、これは for ループ条件がチェックされた後にのみ発生します。この最後のチェックを時間計算量としてカウントする必要があります。これをカウントすると、FOR ループが実際に n+1 回実行されるからです。ここで意味を成しているかどうかはわかりません。数えるべきだと思います。それでも、ここで明確な答えが必要です。提案してください！

4

4 に答える 4

3

本当に正確である必要がある場合は、いくつかの定数を導入してください。ループaの状態を 1 回チェックする時間と、ループb内のすべてのコマンドを実行する時間とします。ループの合計時間は次のとおりです。

a(n+1) + bn = (a+b)n + a

ただし、他の回答で説明されている理由により、これほど正確である必要はほとんどありません。一度に行う時間nよりもはるかに大きい場合は、全体像とは関係ありません。そのため、下位の項と定数をすべて削除して、次のように言います。aa

(a+b)n + a ∈ Θ(n)
于 2013-06-02T08:19:25.550 に答える
1

関数の計算の複雑さを計算する主なポイントは、 nの特定の値に対して関数が何回実行されるかではなく、 nが増加するにつれてその関数が適切にスケーリングされるかどうかを判断することです。たとえば、nが 1 の場合、ループは完全に高速に実行される可能性がありますが、n が突然 1000 になった場合、元の時間の (約) 1000 倍で実行されますか?

あなたが与えたような for ループは常に実行されます - 最悪の場合 - n回。nが 100 であろうと 10^30 であろうと、ループにはn回の繰り返しが含まれます。そのループの余分な比較は、全体像を考えると無関係です。10^30 回の反復を扱っている場合、1 回余分に反復しても違いはありません。

于 2013-06-02T08:19:18.163 に答える
0

時間の複雑さは、定数を考慮して測定されません.. MZF が言ったように.. O(an+c)=O(n) ここで、'a' と 'c' は定数です。しかし、その for ループ内にもう 1 つのループがある場合、時間の複雑さは O(a(n^2) +c) などになります...

于 2013-06-02T09:30:32.023 に答える