java - 这些 for 循环的大 O 表示法是什么？

Question

我正在完成我的类(class)作业，这个特定部分涉及对几个 for 循环的运行时间进行“分析”。讲师指定他想要一个大哦符号答案。

我的构建基础是总运行时间:

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

您可以使用 Sigma 表示法来分析您的算法，以计算/扩展算法内部 for 循环运行的迭代次数:

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;

<小时/>

最后，关于您的问题的说明:

"And last but not least, I am assuming from my textbook that all Triple nested loops are running at N^3 time?"

这不是真的:它取决于如何增加迭代以及每个循环签名中的有界。比较例如上面的 T_a 中的内部循环(以 n^2 为界，但在每次迭代中仅增加 1)或例如the algorithm analyzed in this answer ，或者，对于稍微棘手的情况，the single loop analyzed in this answer .