forループの入れ子になった一連のBig O

Question

私は、forループの外側に入れ子になっている一連のループのBig Oの実行時間の計算について質問があります。例えば

：

 

for (50,000 times) 
{ 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
} 
 

外側のループは一定であるので、私はそれが無視されると思います。次の計算を行うのと同じくらい簡単ですか？

N + N-2 + N + N-2

2N + 2（N-2）

4N - 4

O（4N - 4）

O（ 4N） - -4の定数を取り除いた後

これは正しいですか？

ありがとうございました。

Answer 1

これはO（n）は

（あなたが式の「最大」の部分であるものにのみ関心がある、とあなたは定数を除去）です。あなたは1..nのからループIとi..nからJ内部に別のループを持っていた場合

、それはO（N^2）となります。

Answer 2

これは正しいです。あなたはO(N)という4つのループを追加するだけです。したがって、それは4O(N)であり、それには50, 000が掛けられますが、それは大きい番号ですが、それはNに依存しません。

Answer 3

これはO（N）です。しかし、この文脈では、あなたがNに対して持っているものに依存して、定数はあなたのアルゴリズムの性能に大きな影響を与えるかもしれません。