1

次の関数の時間計算量は?

    for(int i = 0; i < a.size; i++) {
        for(int j = i; j < a.size; i++) {
            //
        }
    }

2 番目の for ループですべての要素を反復処理していないため、大きな O n^2 よりも小さいと思います。時間の複雑さは次のようになると思います。

n[ (n) + (n-1) + (n-2) + ... + (n-n) ]

しかし、この式を解くと、

n^2 - n + n^2 - 2n + n^2 - 3n + ... + n^2 - n^2

これはまったく正しくないようです。誰かがこの問題を解決する方法と、どこが間違っているかを正確に教えてもらえますか?

4

3 に答える 3

2

それはのために実行されます:

1 + 2 + 3 + .. + n

1/2 n(n+1)私たちに与えるのはどれですかO(n^2)

Big-O 表記法は支配的な用語のみを保持し、定数も無視します

Big-O は、支配的な用語が異なる場合にのみ、同じ複雑度分析標準を使用して問題の同じバリエーションのアルゴリズムを比較するためにのみ使用されます。

支配的な項が同じ場合は、ビッグ シータまたは時間の複雑度を比較する必要があります。これにより、わずかな違いが示されます。

ここに画像の説明を入力

例

あ

    for i = 1 .. n
      for j = i .. n
        ..

B

    for i = 1 .. n
      for j = 1 .. n
        ..

我々は持っています

Time(A) = 1/2 n(n+1) ~ O(n^2)

Time(B) = n^2 ~ O(n^2)

O(A) = O(B)

T(A) < T(B)

分析

をどのように取得したかを視覚化するには1 + 2 + 3 + .. n:

    for i = 1 .. n:
      print "(1 + "
      sum = 0
      for j = i .. n:
        sum++
      print sum") + "

以下を出力します。

(1+n) + (1+(n-1)) + .. + (1+3) + (1+2) + (1+1) + (1+0)

n+1 + n + n-1 + .. + 3 + 2 + 1

1 + 2 + 3 + .. + n + n+1

1/2 n(n+1) + (n+1)

1/2 n^2 + 1/2 n + n + 1

1/2 n^2 + 3/2 n + 1
于 2014-05-13T06:00:49.770 に答える
1

はい、反復回数は厳密には 未満ですがn^2、それでもΘ(n^2)です。n^k最終的にはどのよりも大きくなり、最終的にはどのk<2よりも小さくなりn^kますk>2。

(ちなみに、コンピューター科学者は、ビッグシータ (Θ) を実際に意味するとき、ビッグオーと言うことがよくあります。技術的には、これまでに見たほとんどすべてのアルゴリズムにO(n!)実行時間があると言うことは正しいです。合理的なすべてのアルゴリズムの実行時間は、成長しません。しかし、複雑さが であると言うの はn!実際には役に立たないO(n!)ので、ある種のグリセ派の格言によって、誰かがアルゴリズムの複雑さはできるだけ小さいと言ったとき、それは可能な限り小さいと仮定します。) O(n log n)O(f(x))f(x)

于 2014-05-13T05:29:55.260 に答える