带依赖内层索引的嵌套循环时间复杂度计算是否正确？

待分析代码 #

int f(int N) {
    int count = 0;
    for (int i = 1; i < N; i *= 3) {
        for (int j = 1; j < i; ++j) {
            count++;
        }
    }
    return count;
}

现有分析的错误 #

现有分析的结论不正确，存在两个关键错误：

• 误解了内层循环的执行次数：内层循环j的范围是1 <= j < i，因此执行次数是i-1（当i=1时，循环执行0次），而非3^(i-1)。
• 错误使用复杂度相乘规则：外层循环的复杂度是O(logN)，但内层循环的执行次数随i指数增长，不能直接将两层循环的复杂度相乘，必须对所有内层循环的执行次数求和后推导整体复杂度。

正确的时间复杂度推导 #

1. 外层循环的迭代规律：
   外层循环中i的取值序列为1, 3, 9, 27, ..., 3^m，其中3^m < N ≤ 3^(m+1)，因此m = ⌊log₃N⌋，即外层循环共执行m+1次（包含i=1的那次），迭代次数为O(logN)。

2. 总执行次数求和：
   内层循环的总执行次数是各次外层循环对应的内层执行次数之和：
   $$
   S = \sum_{k=1}^m (3^k - 1)
   $$
   （注：当k=0时，3^0=1，内层循环执行0次，因此从k=1开始求和）

   拆分求和项：
   $$
   S = \sum_{k=1}^m 3^k - \sum_{k=1}^m 1
   $$
   利用等比数列求和公式$\sum_{k=1}^m 3^k = \frac{3(3^m - 1)}{2} = \frac{3^{m+1} - 3}{2}$，以及$\sum_{k=1}^m 1 = m$，代入得：
   $$
   S = \frac{3^{m+1} - 3}{2} - m
   $$

3. 最终复杂度确定：
   由于3^m < N ≤ 3^{m+1}，可得3^{m+1} ≤ 3N，代入上式：
   $$
   S ≤ \frac{3N - 3}{2} - m
   $$
   其中m = ⌊log₃N⌋，相对于N是低阶无穷小，可忽略不计。因此总执行次数的时间复杂度为O(N)。

内容的提问来源于stack exchange，提问作者SK_33