循环的增长顺序

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

代码的增长顺序为 O(N^3)。

一般来说，k 个长度为 N 的嵌套循环贡献了 O(N^k) 的增长。

Answer 2

在尝试确定代码的复杂性时，有两件事可能会造成混淆。

并非所有循环都从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).
if语句。 if 语句在这里显然无关紧要，因为它只是最后一个循环的一部分，不包含任何 break 语句或其他会影响循环的代码。它只会影响计数的递增，不会影响任何循环的执行，因此我们可以安全地忽略它。即使计数没有递增（O(1) 操作），也会检查 if 条件（也是 O(1) 操作），因此在使用和不使用if.

因此，即使有if语句，算法仍然是O(N^3).

Answer 3

这里有两个是没怎么计算就发现时间复杂度是Theta(N^3)。

首先，您 select i<j<k 从 0 到 N-1。从 N 中选择 3 个对象的方法数是 binomial coefficient N 选择 3 = N*(N-1)*(N-2)/(3*2*1) ~ (N^3)/6 = O(N^3)，更准确地说是 Theta(N^3).

其次，一个上限是你从N种可能性中选择i、j、k，所以最多有N*N*N = N^3个选择。这是 O(N^3)。您还可以找到相同类型的下界，因为您可以从 0 到 N/3-1 中选择 i，从 N/3 到 2N/3-1 中选择 j，从 2N/3 到 2N/3 中选择 k N-1。这给你至少 floor(N/3)^3 个选择，也就是大约 N^3/27。由于您具有相同形式的上限和下限，因此时间复杂度为 Theta(N^3).

循环的增长顺序

Order of growth for loops

algorithm

time-complexity