2つのネストされたループの時間複雑度

Question

私はアルゴリズムを研究しており、私は解決できない問題に出会った。

for(int i = 0; i < n; i++) 
    for(int j = 0; j < i; j++) 
     sum++; 

したがって、このコードの時間複雑度はn^2です。しかし。最初のループはn回反復され、私はそれを理解しています。しかし、2番目はn（n + 1）/ 2を反復します。それはn *（n（n + 1））/ 2になります。どこが間違っていた？

Answer 1

最初にBig-O表記を理解する必要があります。それはすべての下位条件を投げ、最高のものだけを保持しますN。

外側のループはN回実行されます。したがって、最高の用語はnで、内部ループの最高値はvalueです。それは(n-1)です。

だから、外側のループの Nthの反復のために、あなたは N(N-1) = (N^2 - N)ある内部ループのための、それは二つ_not_/2 '' Nを反復（N + 1）され O(N^2)