如何计算给定两层嵌套循环算法的时间复杂度？

你给出的代码如下：

for (auto i = 0; i < n; ++i) {
    int j = 0;
    while (j * j < i) {
        ++j;
    }
}

复杂度推导过程 #

• 外层for循环共执行n次，遍历i从0到n-1的所有取值
• 对每个固定的i，内层while循环的终止条件是j*j >= i，最终j的取值为⌊√i⌋（向下取整的平方根），因此内层循环单次迭代次数为⌊√i⌋
• 总运算量为所有i对应的内层循环次数之和：
  $$S = \sum_{i=0}^{n-1} ⌊√i⌋$$
• 对求和式做积分近似可得：
  $$\sum_{i=0}^{n-1} √i ≈ \int_{0}^{n} √x dx = \frac{2}{3}n^{\frac{3}{2}}$$
• 因此该算法的时间复杂度为O(n√n)（也可写为$O(n^{\frac{3}{2}})$）

补充说明 #

如果需要降低运算量，可以利用相邻i的平方根非递减的特性，不需要每次循环都把j重置为0：直接保留上一轮i的j结果，下一轮从该值开始递增即可，优化后的总运算量可以降到*O(√n)*量级。

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