2017-06-09 10 views
0
int f(const std::vector<int>& v) {  
    int result = 0; 
    for (int i = 0; i < v.size(); ++i) {    O(N) 
     for (int j = v.size(); j >= 0; j -= 2) {  O(N/2) 
      result += v.at(i) * j; 
     } 
    } 
    return result; 
} 

内側これは例えばランダウの記号の混乱(C++)は、forループ

ため理由v.size()は、次に、10であればしかし、私は、疑問に思って、O(N/2)であります

10> = 0✓

8> = 0✓

6> = 0✓

4> = 0✓

2> = 0✓

0> = 0✓

-2

ループの内側は何午前10

の入力サイズで6回実行することができる失敗します私は行方不明?

EDIT *私は最大の大きさしか考慮していないことを理解します。この質問は、元のO(N/2 + 1)を考え出すことに関するものでした。

+0

内部ループは 'O(N)'です。 'O(N/2)' = 'O(N)'です。定数は、漸近的成長表記の寄与因子ではない。 –

+0

私はこれを理解していますが、O(N/2)がどのように得られたのか不思議です。 – csguy

+0

ロックンロールには十分に近いので、それはまた無関係です。 Nを2倍にすると重要なのは、仕事を倍増させることだけです。 – user4581301

答えて

1

複雑さは、正確な時間ではなく、特定のサイズの入力が完了するまでの時間の大きさを評価する方法を提供しますと一緒に演奏する。複雑さに対処するとき

したがって、あなたが唯一の定数乗算器なしで、最高の大きさを考慮する必要があります。

O(N/2 + 1) = O(N/2) = O(N) 
+0

ああ、答えの鍵はO(n/2)で、私を捨てました。 O(N/2 + 1)ならば最大の大きさが考慮されていると理解しています。 – csguy

+0

ところで、最終的には影響しないので、とにかく 'j == 0 '結果。 – paddy

+0

@ウリエル私はそれがまだ2回実行すると思いますか? 3> = 0、1> = 0、-1は失敗します。 – csguy

0

をコメントでは、あなたが言った:

が、私はこのことを理解し、しかし、私はO(N/2)

を取得する方法としてだけで好奇心、次の表を見てみましょう:

Size of vector  Number of time the inner loop is executed: 
0     1 
1     1 
2     2 
3     2 
... 
100    51 
101    51 
... 
2x     x + 1 
2x + 1    x + 1 

この式の定数1を使用すると、内側ループはO(N/2)になります。