计算具有变量界限的嵌套循环的时间复杂度

Question

我正在尝试确定以下代码片段的时间复杂度，但我不确定如何正确求和内循环的迭代：

k = 1
for i <- 1 to n
 for j = 1, j < n/k , j++
   print
 k = 2k

在此代码中，k 在外循环的每次迭代后加倍。这是我的推理：

外层循环运行n次，所以最初，它的复杂度似乎是O(n) 内循环对 k 的每个值迭代 n/k 次，每次加倍 (k = 1, 2, 4, 8, ...)。所有外循环迭代中内循环的迭代总数可以表示为序列 n+n/2+n/4+n/8+... 该级数是几何级数，其和收敛于2n。鉴于此，完成的总工作似乎与 2n 成正比，表明其复杂度是线性的。

问题：我在计算级数总和时是否误解了某些内容，或者为什么这不会导致最初出现的 O(n^2) 复杂度？有人可以澄清这段代码的正确时间复杂度吗？

Answer 1

我在计算系列总和时是否误解了什么？

不，你的分析是正确的。

为什么这不会导致最初出现的 O(n^2) 复杂度？

正如您所分析的，内循环不会迭代那么多次，并且迭代总数不会超过 2𝑛。

一个示例还可以让您“感觉”这些迭代有多么少。当 𝑛 为 1000 并且 𝑖 达到 11（在 1, 2, ..., 10 之后）时，𝑘 将加倍到 2

10 = 1024，因此内循环不会进行任何迭代，如 𝑛/𝑘小于 1。现在意识到，对于 12 到 1000 之间的所有 𝑖 值，此 𝑛/k 都小于 1，因此在所有这 990 种情况下，内部循环不会进行任何迭代。 ^{但是你指向几何级数的分析才是迭代总数不超过2𝑛的真实证明。}

加上外循环迭代次数的开销（例如计算

i <= n

的次数（𝑛+1 次），你会得到 O(3𝑛)，它仍然是 O(𝑛)。

为了说明这一点，您可以实现代码并继续执行以获得更大的输入，并查看 𝑛 的值与完成的工作（使用计数器）之间的比率如何表现：

function f(n) {
    let k = 1;
    let count = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j < n/k; j++) {
            count++; // Work done (e.g. to evaluate j < n/k and increment j)
        }
        k = 2 * k;
        count++; // Work done (e.g. to evaluate i <= n, k = 2 * k and the failing j < n/k)
    }
    return count;
}

let n = 0;
setInterval(() =>
    console.log(++n, f(n) / n) // Ratio approaches a constant
);