3

次のコードのBig-OはO（n）またはO（log n）ですか？

for (int i = 1; i < n; i*=2)
        sum++;

O（n）のように見えますか、それとも私はこれを完全に見逃していますか？

4

6 に答える 6

10

毎回2倍になるO(logn)のでです。したがって、全体として、までiを繰り返す必要があります。この場合は、（以降）のときに発生します。k2^k = nk = logn2^logn = n

簡単な例：仮定n = 100-次に：

iter1: i = 1
iter2: i = 2
iter3: i = 4
iter4: i = 8
iter5: i = 16
iter6: i = 32
iter7: i = 64
iter8: i = 128 > 100

が2倍になると反復が追加されることは簡単にわかりますn。これは対数の振る舞いですが、線形の振る舞いは。の一定の増加に対して反復を追加しますn。

PS（編集）： 数学的に言えば、アルゴリズムは確かに-big O(n)-O表記は漸近的な上限を与えるので、アルゴリズムは漸近的に「より速く」実行されますO(n)-したがって、それは確かにO(n)-ですが、厳密な境界ではありません（そうではありませんTheta(n)）それが実際にあなたが探しているものだとは思えません。

于 2012-08-20T06:51:05.683 に答える
3

ループは（log 2 n-1）回実行されるため、複雑さはO（logn）です。

于 2012-08-20T06:51:35.157 に答える
2

O（log（n））、ループするのは〜log2（n）回だけなので

于 2012-08-20T06:51:18.300 に答える
1

いいえ、複雑さは線形ではありません。いくつかのシナリオを試してみてください。このサイクルは、n = 2、n = 4、n = 16、n = 1024に対して何回の反復を行いますか？n = 1024 * 1024の場合はどうですか？多分これはあなたが正しい答えを得るのを助けるでしょう。

于 2012-08-20T06:51:21.770 に答える
0

forループチェックはlg（n）+1回実行されます。内側のループはlg（n）回実行されます。したがって、複雑さはO（log n）ではなくO（lg n）です。

n == 8の場合、コードは次のように実行されます。

  1. i = 1
  2. i = 2
  3. i = 4
  4. i=8--終了条件
于 2012-08-20T06:54:11.257 に答える
0

O（log（n））です。コードnum++を見てください。O（log（n））回ループします。

于 2012-08-20T07:04:21.313 に答える