嵌套不同循环结构的时间复杂度

Question

我有一段代码以下列方式执行三个嵌套的 for 循环（尽可能写成与语言无关的形式）：

for i = 0 to n - 1
    for j = 0 to n - 1
        for k = 0 to n - 1
            [do computation in linear time]

我的直觉告诉我这会导致 N^3 的复杂度。我想将其复杂性与以下嵌套循环进行比较：

for i = 0 to n - 1
    for j = i + 1 to n - 1
        for k = j + 1 to n - 1
            [do computation in linear time]

从逻辑上讲，它应该更快，因为随着 i 的增加，内部循环应该计算得更快；然而，在网站上看到无数其他线程解释后者也是 N^3 令人困惑。

我对两者的 N^3 假设是否正确？如果是这样，假设存在差异，我该如何量化差异？

Answer 1

使用大 O 表示法，仅列出前导多项式值（即，在本例中为 N^3）。您提供的后一个示例可以描述为 a(N^3)-b(N^2)-c(N)-d，其中 {a,b,c,d} 是整数，因此后者可能显着更快取决于 i 或 n 的大小。但是，因为您有 3 个嵌套循环，所以 big-O 表示法仍将列为 N^3。

Answer 2

以上代码的时间复杂度都是 n^3 的阶数，即 Big O (n^3)。根据大 O 符号的定义，对于某个常数 k，T(n) ≤ k f(n)。因此，第二个代码对某个常数 k 的贡献不会太大。

Time complexity for nested for different loop structures