这段嵌套循环代码的正确时间复杂度是什么？求θ复杂度解析

先给结论：这段代码的θ复杂度是θ(n)，不是你一开始想的θ(n logn)，原因在于内层循环的执行次数会随着外层变量i的增大而快速减少，整体求和后主导项是线性的n，而非n logn。

具体拆解分析：

• 外层循环：i从2到n-1，总共执行n-2次，近似为θ(n)次。
• 内层循环：对于每个i，j从1开始每次乘i，直到j >=n停止，执行次数是满足i^k <n的最大整数k，也就是k = floor(log_i n)（以i为底n的对数）。

现在把内层循环的总次数拆成两部分计算：

1. 当i <= sqrt(n)时：这部分的i最多有sqrt(n)个，每个内层循环的最大次数是log_2 n（当i=2时），所以这部分的总执行次数是O(sqrt(n) * logn)——这个量级远小于n，属于低阶项，可以忽略。
2. 当i > sqrt(n)时：这部分的i有大约n - sqrt(n)个（接近n个）。此时i^2 >n（因为i>sqrt(n)，平方后必然大于n），所以内层循环只会执行2次：第一次j=1（满足j<n），count++；第二次j=i（仍然满足j<n，因为i<n），count++；第三次j=i*i >=n，退出循环。这部分的总执行次数是O(n)，是主导项。

把两部分加起来，总次数的主导项是n，低阶项sqrt(n)logn可以忽略，所以整体复杂度是θ(n)。

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