几何级数序列时间复杂度解析：代码O(N)复杂度的疑惑

先看你给出的代码：

int sum = 0;
for (int i=1; i<n; i=i*3) {
    for (int j=1; j<=i; j++) {
        sum++;
    }
}

你的误区在于错误地将外层循环次数和内层循环的“单次复杂度”相乘，实际上我们需要计算所有内层循环的总执行次数，而非简单乘法。

步骤1：分析外层循环的i取值 #

外层循环中，i的取值依次是1, 3, 9, 27, ..., 3^k，直到3^k < n停止。这里k的取值满足3^k < n ≤ 3^(k+1)，k的数量级是O(log₃n)，也就是O(logn)（对数的底数不影响时间复杂度的大O表示）。

步骤2：计算内层循环的总执行次数 #

每次外层循环对应的内层循环会执行i次，总执行次数是这些i值的和：

S = 1 + 3 + 9 + ... + 3^k

这是首项为1、公比为3的等比数列，求和公式为：

S = (3^(k+1) - 1) / (3 - 1) = (3^(k+1) - 1)/2

步骤3：推导总次数的数量级 #

因为3^k < n，所以3^(k+1) = 3*3^k < 3n，代入求和公式可得：

S < (3n - 1)/2 < 3n/2

这意味着总执行次数的上限是线性的，也就是O(n)，所以这段代码的时间复杂度是O(N)。

内容的提问来源于stack exchange，提问作者Student-san