如何确定具有嵌套循环的算法的计算复杂度？

Question

在查看了这个 question, this article 和其他几个问题之后，我仍然无法找到一种通用方法来确定具有依赖于父循环变量的循环变量的算法的计算复杂度。例如，

   for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
           for (int k = i; k < j; k++) {
               //one statement
           }
       }
   }

我知道第一个循环的复杂度为 n，但内部循环让我感到困惑。第二个循环似乎执行了 n-i 次，第三个循环似乎执行了 j-i 次。但是，我不确定如何将其变成常规的 Big-O 语句。我不认为我可以说 O(n(n-i)(j-i))，所以我怎样才能去掉这里的 i 和 j 变量？

我知道这是 n^3 的顺序，但我该如何显示呢？我需要使用系列吗？

感谢您的帮助！

（如果您想知道，这是来自最大和连续子序列问题的蛮力实现。）

Answer 1

第一个循环平均命中 N 个项目。
第二个循环平均命中 N / 2 个项目
第三个循环平均命中 N / 4 项

O(N * N / 2 * N / 4) 大约是 O((N^3)/8) 大约是 O(N^3)

如何确定具有嵌套循环的算法的计算复杂度？

How to determine computational complexity for algorithms with nested loops?

algorithm

complexity-theory

big-o