4

私は最近、このプリンストン コースのアルゴリズムを使い始めましたが、次のパターンを観察しました。

オン）

 double max = a[0];
  for (int i = 1; i < N; i++)
     if (a[i] > max) max = a[i];

O(N^2)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        if (a[i] + a[j] == 0)
           cnt++;

O(N^3) 

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; k++)
           if (a[i] + a[j] + a[k] == 0)
cnt++;

ここでの一般的なパターンは、ループ内のネストが大きくなるにつれて、指数も大きくなるということです。20 個の for ループがある場合、複雑さは 0(N^20) になると想定しても安全ですか?

PS: 20 は私が選んだ単なる乱数であることに注意してください。はい、コード内で 20 の for ループをネストすると、明らかに何か問題があります。

4

5 に答える 5

2

はい、ループの長さが比例しN、説明したようにループが互いにネストされている場合。

于 2013-08-13T17:35:14.600 に答える
1

あなたの特定のパターンでは、はい。しかし、一般的にそれを想定するのは安全ではありません。囲んでいるすべてのループの状態に関係なく、各ループの反復回数が O(n) であるかどうかを確認する必要があります。これが事実であることを確認して初めて、複雑さが O(n loop-nesting-level )であると結論付けることができます。

于 2013-08-13T17:35:02.107 に答える
0

はい。繰り返しの間隔を減らしても、Big-o 表記法は N が無限に向かって増加するように機能し、すべてのループの長さが N に比例して増加するため、そのようなアルゴリズムの時間の複雑さは O(N^20) になります。

于 2013-08-13T17:33:33.577 に答える
0

各ループが 0 から N まで実行される二重にネストされたループが O(N^2) である理由を理解することを強くお勧めします。合計を使用して、for ループに含まれるステップ数を評価し、定数と低次項を削除します。そのアルゴリズムの Big-Oh を取得します。

于 2013-08-13T17:41:55.453 に答える