这些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。