これらのforループのBig O表記法とは何ですか？

Question

私はクラスの課題を仕上げていますが、この特定のセクションではいくつかのforループの実行時間の「分析」を行います。指導者はビッグ・オノー表記の答えが必要だと指定しました。

total = 0; 

    for (int i = 0; i < n;i++){ 
    total++; 
} 

は、回答：：O（N）その実行の線形私がいることを知っている

1)The cost of executing each statement 
2)The frequency of execution of each statement 
3)The idea of working from "inside and out", specifically starting from inner loops. 

：

私は時間を実行している合計基盤の上に構築していますがに基づいています。

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

回答：O（N^2）は、Nがどれだけ大きくなるかだけを気にします。

私は

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

と

for (i = 0;i < n;++i) 
    for (j = 0; j < i;++j) 
    ++total; 

そして最後に混乱していなく、少なくとも、私はすべてのトリプルネストされたループがNに^ 3時間を実行していることを私の教科書から想定していますか？

あなたのアルゴリズムのforループの内側で実行反復回数/カウント拡大して、シグマの表記を使用してアルゴリズムを解析することができ

Answer 1

：

T_aが

for (i = 0; i < n; ++i) 
    for (j = 0; j < n * n; ++j) 
     ++total; 

カバーおよびT_b：

for (i = 0; i < n; ++i) 
    for (j = 0; j < i; ++j) 
     ++total; 

---

最後に、あなたの質問に注記：

「そして最後にではなく、少なくとも、私はすべての トリプルネストされたループがN^3時に実行されているというのが私の教科書から想定しています？」

これは真実ではない：それは反復がを増加させるだけでなく、が各ループの署名に有界方法に依存します。例：内ループはで囲まれているが、各反復では単に1だけ増加している。 the algorithm analyzed in this answer、またはややトリッキーな場合はthe single loop analyzed in this answerです。