内层循环Big O复杂度分析求助：已知外层O(n)、内层二O(logn)，求内层三复杂度

先把我们要分析的代码贴出来，方便对照：

for(i=0;i<n;i+=2) { 
    for(j=1;j<i*i;j*=3) { 
        for(k=2;k*k<=n;k++){} 
    } 
}

我们来逐层拆解每个循环的复杂度，再把它们组合起来：

1. 外层循环 #

外层循环是 for(i=0;i<n;i+=2)：i从0开始，每次跳2，直到超过n。总迭代次数大概是 n/2，忽略常数系数后，复杂度是 O(n)，这和你已经知道的一致。

不过要注意：当i=0时，i*i=0，第二个内层循环的条件j<0不成立，所以这一次外层循环不会执行任何内层逻辑，可以直接忽略。

2. 第二个内层循环（j循环） #

这个循环是 for(j=1;j<i*i;j*=3)：j从1开始，每次乘以3，直到j不小于i²。这种“每次乘常数”的循环，次数是对数级的——具体来说，循环次数等于满足 3^m < i² 的最大m值，也就是 m ≈ log₃(i²) = 2log₃i。忽略常数系数和对数的底数（底数不影响Big O的量级），这个循环的复杂度是 O(log i)。

当i最大到n时，log i的上限是log n，所以你提到的O(log n)是这个循环的最坏情况单次复杂度，完全没问题。

3. 第三个内层循环（k循环） #

你之前不确定这个循环的复杂度，其实很好推导：循环条件是k*k <=n，也就是k最多到√n（当k=√n时，k²=n，刚好满足终止前的最后一次循环）。k从2开始，到√n结束，总迭代次数大约是√n - 1，忽略常数后，复杂度是 O(√n)。

这里要划重点：这个循环的终止条件只和n有关，和外层的i、j都没关系——也就是说，不管i和j是什么值，每次执行这个循环的次数都是固定的O(√n)。

总复杂度计算 #

现在把三层循环的复杂度组合起来：

• 外层循环执行O(n)次有效迭代
• 每一次外层循环里，第二个循环执行O(log i)次
• 每一次第二个循环里，第三个循环执行O(√n)次

总操作数可以简化为：O(√n) * 求和（i从2到n，步长2）O(log i)

而从1到n的log i求和结果是O(n log n)，步长2的求和相当于取一半的项，结果还是O(n log n)。所以总复杂度就是：
O(√n) * O(n log n) = O(n^(3/2) log n)

简单说，最终的Big O复杂度是 O(n√n log n)（或者写成O(n^1.5 log n)，两种写法都被广泛接受）。

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