请问以下C++代码的时间复杂度（大O表示法）如何分析？

先看代码结构：三层嵌套循环，核心操作是++cnt，我们需要计算这个操作的总执行次数，再用大O表示法描述渐近复杂度。

步骤1：拆解每层循环的有效范围 #

• 最内层循环：k从j*j开始到n-1，只有当j*j < n（即j < √n）时，循环才会执行；如果j >= √n，j*j >=n，内层循环执行0次。
• 第二层循环：j从i到n-1，但只有j < √n的部分会触发内层循环，因此有效范围是j ∈ [i, min(n-1, floor(√n)-1)]。
• 第一层循环：i从1到n-1，但当i >= √n时，j从i开始必然j >= √n，内层循环无执行，因此有效范围是i ∈ [1, floor(√n)-1]。

步骤2：计算核心操作的总次数 #

我们只需要考虑i <= √n且j <= √n的情况：

• 对于每个有效i，j的有效取值数量约为√n（因为j从i到√n，最多√n个值）。
• 每个有效j对应的内层循环执行次数约为n（因为k从j²到n-1，j²最多是n，所以循环次数接近n）。

总执行次数的上界：√n * √n * n = n²，即总次数不会超过n²的常数倍。

同时可以找下界验证：当i <= √n/2、j <= √n/2时，j² <= n/4，内层循环执行次数至少为n - n/4 = 3n/4，这部分的总次数约为(√n/2) * (√n/2) * 3n/4 = 3n²/16，说明总次数至少是n²的常数倍。

结论 #

这段代码的时间复杂度为O(n²)（精确来说是Θ(n²)）。

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