循环增长顺序

Question

以下代码的增长顺序是什么？我的猜测是,每个循环的增长是线性的,但if语句让我感到困惑.我如何将其与整个事物包括在一起.我非常感谢解释性答案,以便我能理解所涉及的过程.

int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if(a[i] + a[j] + a[k] == 0)
count++;

Answer 1

在尝试确定代码的复杂性时，有两件事可能会令人困惑。

1. 事实上，并非所有循环都从 0 开始。第二个循环从 开始i + 1，第三个循环从 开始j + 1。这会影响复杂性吗？它不是。我们只考虑前两个循环。对于i = 0，第二个运行N - 1次，因为i = 1它运行N - 2次，...，因为i = N - 1它运行0次。将所有这些加起来：

   0 + 1 + ... + N - 1 = N(N - 1) / 2 = O(N^2).
   

   所以不从 0 开始不会影响复杂性（记住 big-oh 忽略低阶项和常数）。所以，即使是在这样的设定下，整个事情也是如此O(N^3)。

2. 该if声明。该if语句显然与此处无关，因为它只是最后一个循环的一部分，并且不包含break会影响循环的语句或其他代码。它只影响计数的递增，而不影响任何循环的执行，因此我们可以放心地忽略它。即使计数没有增加（一个O(1)操作），if也会检查条件（也是一个O(1)操作），因此使用和不使用 . 执行的操作数量大致相同if。

   因此，即使有这样的if说法，算法仍然是O(N^3)。