嵌套循环时间复杂度咨询：变量每次翻倍的复杂度是否为O((logn)^2)

代码片段 #

for (i = 1; i <= n; i *= 2) 
{ 
    for (j = 1; j <= i; j *= 2) 
    {
        // SOME TASKS 
    } 
}

问题与AI结论 #

请问这段代码的时间复杂度是多少？生成式AI给出的结果是O((logn)^2)，该结论是否正确？

AI给出的推导过程如下：

我们可以将整体时间复杂度表示为：∑_{i=1,2,4,…,n} O(log⁡i)
该求和式近似等于：O(log⁡1+log⁡2+log⁡4+⋯+log⁡n)
利用对数性质可简化为：O(log⁡n⋅log⁡n)=O((log⁡n)^2)
最终答案
这段代码的总时间复杂度为：O((log⁡n)^2)

严谨推导验证 #

AI的结论是正确的，以下是详细推导过程：

1. 外层循环迭代次数：
   外层循环中i从1开始，每次乘以2直至i ≤n。设迭代次数为k，则满足2^(k-1) ≤n <2^k，因此k = ⌊log₂n⌋ +1，显然k属于Θ(logn)量级。

2. 内层循环迭代次数：
   对于外层循环的第m次迭代（从0开始计数），此时i=2^m。内层循环j从1开始乘以2，直至j ≤i，迭代次数为log₂i +1 = m+1次（例如i=2^m时，j的取值为1,2,...,2^m，共m+1个值）。

3. 总操作次数求和：
   总操作次数等于外层每次迭代对应的内层次数之和，即：

总次数 = 1 + 2 + 3 + ... + k = k*(k+1)/2

由于k是Θ(logn)，代入后总次数为Θ((logn)^2)，因此时间复杂度为O((logn)^2)。

同类问题思路适配 #

对于这类嵌套指数循环问题，核心是将循环变量的指数形式转化为整数变量（比如把i=2^m转化为m的取值范围），将求和式转化为连续整数的求和，这和同类问题的核心分析思路完全一致。

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