algorithm - 这个三重嵌套循环的大 O？

Question

这有什么大不了的？

for (int i = 1; i < n; i++) {
    for (int j = 1; j < (i*i); j++) {
        if (j % i == 0) {
            for (int k = 0; k < j; k++) {
                // Simple computation
            }
        }
    }
}

实在想不通。倾向于说 O(n^4 log(n)) 但感觉我在这里错了。

Answer 1

这是一个相当令人困惑的分析，所以让我们一点一点地分解它以理解计算:

最外层循环运行 n-1 次迭代(因为 1 ≤ i < n)。
它内部的下一个循环对外部循环的每个索引 i 进行 (i² - 1) 次迭代(因为 1 ≤ j < i²)。

总的来说，这意味着这两个循环的迭代次数等于为每个 1 ≤ i < n 计算 (i²-1) 的总和。这类似于 computing the sum of the first n squares , 并且是 O(n³) 的数量级。请注意，模运算符 % 需要常数时间 (O(1)) 来计算，因此检查条件 if (j % i == 0) 这两个的所有迭代循环不会影响 O(n³) 运行时间。

现在我们来谈谈条件语句中的内循环。
我们很想知道这个 if 条件计算为真多少次(以及 j 的哪些值)，因为这将决定最内层循环将运行多少次迭代。实际上，如果 j < i，(j % i) 永远不会等于 0，因此第二个循环实际上可以缩短为从 i 开始而不是从 1 开始，但这不会影响算法的 Big-O 上限。
请注意，对于给定的数字 i，(j % i == 0) 当且仅当 i 是 j 的约数。由于我们的范围是 (1 ≤ j < i²)，因此对于任何给定的 i，j 的总共有 (i-1) 个值是正确的。
如果这令人困惑，请考虑以下示例:

假设 i = 4。那么我们的索引 j 将遍历所有值 1,..,15=i²,并且 (j%i == 0) 对于 j = 4, 8, 12 - 恰好 (i - 1) 个值是正确的。因此，最内层循环总共进行 (12 + 8 + 4 = 24) 次迭代。
因此，对于一般索引 i，我们将寻找总和:i + 2i + 3i + ... + (i-1)i 以指示最内层循环将进行的迭代次数。

这可以通过计算等差级数的总和来推广。第一个值是 i，最后一个值是 (i-1)i，这导致每个 i 值的 k 循环的 (i³ - i²)/2 次迭代的总和。反过来，可以通过计算立方和和平方和来计算 i 所有值的总和 - 对于最内层循环的 O(n⁴) 次迭代的总运行时间( k 循环)对于 i 的所有值。

因此，总的来说，该算法的运行时间将是我们上面计算的两个运行时间的总和。我们检查了 if 语句 O(n³) 次并且最里面的循环运行了 O(n⁴)，所以假设 //Simple computation 在恒定时间内运行，我们的总运行时间将归结为:

O(n³) + O(n⁴)*O(1) = O(n⁴)