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

有人可以帮我完成第四步和第五步吗？当 k 从 1 变为 (i+j) 时，这真的很令人困惑。

标签： algorithmmath

Answer 1

我们可以用数学方法证明复杂性。迭代总数可以表示为（不幸的是不支持乳胶）

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))