嵌套依赖三重循环的时间复杂度（大O表示法）求解咨询

嘿，先给你点个赞，你对最内层k循环的思路是对的！不过得先提个小细节：你给出的代码里，k循环初始值是0且每次更新为k=k*2，这会导致k永远是0，循环无限执行；j循环的更新是j=j/2，当j降到0后也会一直循环下去，这显然不是一个能终止的有效算法。我推测这是笔误，比如k的初始值应该是1，j循环的终止条件应该是j>=1（不然没法正常结束）。下面我基于能正常终止的合理场景来分析，完全贴合你提到的j=j/2的更新规则~

第一步：确认最内层k循环的复杂度 #

假设k循环修正为for(int k=1;k<=n;k=k*2)，那每次k翻倍，从1到n的执行次数是log₂n + 1，忽略常数项后确实是O(log n)，你的分析完全正确！

第二步：拆解i和j的嵌套循环 #

现在看外层i循环（从0到n，共n+1次，近似n次）和内层j循环（初始j=i，每次j=j/2，直到j<1终止）：

• 当i=0时，j=0，循环会无限执行，这里我们忽略这种边界情况（实际代码里肯定会修正，而且n很大时不影响整体复杂度）。
• 当i≥1时，j的取值序列是i, i/2, i/4, ..., 1，执行次数等于把i不断除以2直到得到1的次数加1，也就是log₂i + 1次（比如i=8时，j=8→4→2→1，共4次，log₂8+1=4）。

接下来计算i从1到n时，j循环的总执行次数：
$$\sum_{i=1}^n (\log_2 i + 1) = \sum_{i=1}^n \log_2 i + \sum_{i=1}^n 1$$

• 第二项$\sum_{i=1}^n 1 = n$，复杂度是O(n)。
• 第一项$\sum_{i=1}^n \log_2 i = \log_2(n!)$，根据斯特林公式，$n! \approx n^n e^{-n} \sqrt{2\pi n}$，取对数后可得$\log_2(n!) \approx n\log_2 n - \frac{n}{\ln 2}$，复杂度是O(n log n)。

把两项加起来，i和j嵌套循环的总复杂度是O(n log n) + O(n) = O(n log n)（因为n log n的增长速度远快于n）。

第三步：计算总时间复杂度 #

算法的总复杂度是三个循环复杂度的乘积（因为每个外层循环的迭代都会触发内层循环的所有迭代）：
$$O(n \log n) \times O(\log n) = O(n (\log n)^2)$$

如果j循环是另一种笔误（j=j*2） #

如果你本来想写的是j每次翻倍（j=j*2），直到j>n，那j循环的执行次数是$\log_2(\frac{n}{i}) +1$，总执行次数的总和是O(n)，此时总复杂度就是O(n) × O(log n) = O(n log n)。

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