複数の線形演算が全体の関数に悪影響を及ぼします。

Question

これはやや単純な質問のかもしれないですが、私はとにかく人々を依頼するつもりです：

私は、以下の機能を書いた：

std::vector<int> V={1,2,3,4,5}; 
int myFunction() 
{ 
    for(int i=V.size();i--;){//Do Stuff}; 
    for int e=V.size();i--;){//Do Stuff}; 
} 

を。これは、時間複雑最悪の場合を持っている必要がありますO （n）およびより複雑なケースO（1）。

2つの線形演算（for-loops）を持つと、時間の複雑さはO（n）以外に変わるのですか？

Answer 1

番号です。 O(N)は、aN+b + something weaker than linear Nのような意味です。

T(N)= 5N+100 + Log(N)のようなものでも、O(N)とみなされます。

O(N) = aN+b + R(N) 

---

：だからO(N)のように書くことができ

lim R(N)/N = 0 ; N-->Inifinity //Use L'Hospital's Rule for solving these kind of limits 

：式を満たす "リニアNよりも弱い何か"、私が意味する任意の関数R（N）によって

サイドノート：複雑さはパフォーマンスと等しくありません。 (N+N)はまだO(N)ですが、これは(N)より遅くないことを意味しません。パフォーマンスは、最も基本的な形では、理論上の複雑さではなく何かを行うために必要なサイクル数です。

しかし、少なくともNが非常に大きな数値（ほとんど無限大）になるときは関連している必要があります。