嵌套循环算法时间复杂度疑问：推导与实测O(n)结果不符？

待分析代码 #

int algo(int n) {
    int count = 0;
    for(int i = 1; i < n; i++)
        for(int j = i; j <= n; j *= 2)
            count++;
    return count;
}

问题描述 #

我自行推导了该算法的时间复杂度，但运行代码后发现其实际时间复杂度约为2n，即O(n)。想问是计算错误，还是推导表达式可进一步简化？

分析结论 #

你的推导没有错误，只是推导得到的表达式可以进一步化简，最终的渐进时间复杂度确实是O(n)，和你运行代码观察到的结果一致。

具体化简逻辑如下：

1. 外层循环i从1到n-1，每个i对应的内层循环次数为floor(log₂(n/i)) + 1——j从i开始每次乘2，直到超过n，次数等于满足i*2^k ≤n的最大k值加1。
2. 总执行次数T(n)可拆分为两部分求和：
   • 第一部分：Σ（i=1到n-1）1 = n-1
   • 第二部分：Σ（i=1到n-1）floor(log₂(n/i))
3. 对第二部分换角度统计：按k=log₂(n/i)的取值，统计每个k对应的i的数量再求和。展开后会出现大量抵消项，最终可推导出T(n) ≤ 2n - O(logn)。
4. 忽略低阶项和常数后，渐进时间复杂度就是O(n)，和你观察到的“约为2n”的线性增长趋势完全匹配。

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