首先得先提个关键问题：你的代码里当i=0时，内层循环会无限运行——因为j的步长是0，j永远停在0，永远满足j < n的条件，这是个严重的bug，得先修正这个情况（比如把外层循环改成i从1开始，或者在i=0时跳过内层循环），不然这段代码根本没法正常执行。

假设我们修正了这个问题，让外层循环的i从1到n-1，那我们来一步步拆解时间复杂度：

• 对于每个i，内层循环的执行次数是多少？
  内层循环里j从0开始，每次加i，直到j < n。比如当i=1时，j会取0、1、2…n-1，共n次；当i=2时，j取0、2、4…直到小于n，大概是n/2次；当i=k时，内层循环的次数约等于n/k次（取整后和这个值的差可以忽略，不影响复杂度分析）。

• 总执行次数就是所有i对应的内层次数之和：
  总次数≈Σ（i从1到n-1）的n/i，这个求和式其实是n乘以调和级数。调和级数Σ（i=1到n）1/i的近似值是ln n + γ（γ是欧拉常数，约0.577），所以总次数≈n*(ln n)，对应的时间复杂度是O(n log n)，远小于你之前以为的O(n²)。

为什么不是O(n²)？因为当i越大时，内层循环的次数越少——比如i接近n的时候，内层循环只执行1-2次，而不是n次。只有当i很小的时候（比如i=1），内层循环才会执行n次，但大部分i对应的次数都远小于n，所以总和不是n×n，而是n乘以对数级别的数。

如果不修正i=0的问题，那这段代码直接死循环，时间复杂度就是无穷大了，这肯定不是你想要的情况。

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