algorithm - 查找嵌套循环的复杂性

Question

所以我有一个非常复杂的嵌套循环，我需要找到它的复杂性。代码如下:

1. int c = 0;
2. for (int i = 1; i <= n; i++)
3.   for (int j = 1; j <= n; j++)
4.     for (int k = 1; k <= i + j; k += 3)
5.       c++;
6. return c;

所以我知道复杂度在 O(n^3) 中，但我需要知道如何进行数学证明。下面显示了每行的执行频率。

1. 1
2. n
3. n(n-1)
4. No idea how to do this
5. No idea
6. 1

有人可以帮我解决第 4 步和第 5 步吗？当 k 从 1 到 (i+j) 时，这真的很令人困惑。

Answer 1

我们可以从数学上证明复杂性。迭代总数可以表示为(不幸的是不支持 latex )

sum_j=1^n sum_i=1^n (i + j) / 3

如果绘制 i 和 j 值及其总和 i + j 的网格，您也可以看到这一点。

这相当于

sum_j=1^n {[n(n + 1)/2 + nj] / 3}

可以进一步简化为

{n[n(n + 1)/2] + n[n(n + 1)/2] / 3}

评估后给出

(n^3 + n^2) / 3

这是 O(n^3) 的顺序。

步骤为 1 而不是 3 的迭代次数可以通过编程方式证明(Python 代码)

c = 0
n = 4 # change n for testing, slow
for i in range(1, n + 1):
  for j in range(1, n + 1):
    for k in range(1, i + j + 1):
      c += 1
assert(c == (n ** 3 + n ** 2))