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

Question

外循环是 O(n)，第二个循环是 O(n^2)，第三个循环也是 O(n^2)，但第三个循环是有条件的。

这是否意味着第 3 次循环只发生 1/n(每 n 次 1)次，因此总的大 O 是 O(n^4)？

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

Answer 1

对于 1 到 n 之间的任何给定 i 值，这部分的复杂度:

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

是O(ⁿ⁴/_i)，因为if-条件有 i 次为真。 (注意:如果 i 可以大于 n，那么我们需要写成 O(ⁿ⁴/_i + n²) 以包括循环迭代的成本，其中if 条件为假；但由于已知 i 足够小 ⁿ⁴ /_i ≥ n²，我们不需要担心这个。)

因此，将所有 i 值的不同循环迭代加在一起，代码的总复杂度为 O(ⁿ⁴/₁ + ⁿ⁴/ ₂ + ⁿ⁴/₃ + ⋯ + ⁿ⁴/_n) = O(n< sup>4 · (¹/₁ + ¹/₂ + ¹/₃ + ⋯ + ¹/_n)) = O(n⁴ log n)。

(最后一点依赖于这样一个事实，因为 ln(n) 是 ¹/_{x 的积分/sub> 从 1 到 n，并且 ¹/x 在该区间内递减，我们有 ln( n) < ln(n+1) < (¹/1 + ¹/2 + ¹/3 + ⋯ + ¹/n) < 1 + ln(n).)}