这段代码的Big-O时间复杂度是多少？含Boo()复杂度分析疑问

待分析代码 #

for( i = 1; i < n; ++i )
    for( j = 1; j < i * i; ++j )
        if( j % i == 0 )
            Boo();

问题 #

假设Boo()的时间复杂度为O(n²)，上述代码块的总Big-O时间复杂度是多少？

原分析的问题 #

原分析认为外层循环O(n)、内层循环O(n²)、if语句O(n)，总复杂度为n * n² * n * n² = O(n⁶)，这个逻辑完全错误——它错误地将所有环节的复杂度直接相乘，忽略了if(j % i == 0)的触发频率，没有区分内层循环总次数和Boo()的实际执行次数。

正确推导过程 #

1. 外层循环：i从1遍历到n-1，共O(n)次迭代。
2. Boo()的执行次数：对于每个i，内层循环中只有当j是i的倍数时才会执行Boo()。j的取值范围是1到i²-1，满足j % i == 0的j可表示为ki（k为正整数），此时k的上限是i-1（因为ki < i² → k < i）。所以每个i对应的Boo()执行次数是i-1次，近似为O(i)。
3. 总执行次数求和：对i从1到n-1的执行次数求和，即1 + 2 + 3 + ... + (n-1) = n(n-1)/2，这属于O(n²)级别的总次数。
4. 总时间复杂度：每次Boo()的复杂度是O(n²)，因此总复杂度为O(n²) * O(n²) = O(n⁴)。

结论 #

这段代码的总Big-O时间复杂度为O(n⁴)。

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