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)を考え出すことに関するものでした。
内部ループは 'O(N)'です。 'O(N/2)' = 'O(N)'です。定数は、漸近的成長表記の寄与因子ではない。 –
私はこれを理解していますが、O(N/2)がどのように得られたのか不思議です。 – csguy
ロックンロールには十分に近いので、それはまた無関係です。 Nを2倍にすると重要なのは、仕事を倍増させることだけです。 – user4581301