這些for循環的大O符號是什麼？

Question

我正在完成我的課程作業，這部分內容涉及對幾個for循環的運行時間進行「分析」。教練指定他想要一個Big Oh Notation答案。

我對總運行時間的基礎上建立的依據是：

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. 

我知道：

total = 0; 

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

答：O（N）的運行線。

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運行時間假設？

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運行時間假設」

這是不正確的：這取決於的迭代是如何增加以及在每個循環的簽名界。比較例如其中內環T_a以上（以n^2爲界，但在每次迭代中僅增加1）或例如the algorithm analyzed in this answer，或者對於稍微棘手的情況，the single loop analyzed in this answer。