这个嵌套循环的复杂性是多少，其中两个循环变量每次迭代都会加倍？

Question

以下代码片段的时间复杂度是多少？

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

我查阅了一些GenAI，结果表明会是

O((logn)^2)

。但这是正确的吗？ GPT 和 Claude 给了我以下答案：

我们可以将整体时间复杂度表示为： Σ_{i=1,2,4,…,n} O(logu2061i)

这个总和大致等于：O(logu20611+logu20612+logu20614+⋯+logu2061n)

利用对数的性质，我们可以将其简化为：O(logu2061n⋅logu2061n)=O((logu2061n)^2)

最终答案

此代码的总时间复杂度为：O((logu2061n)^2)

我遵循了Stack Overflow 上的类似问答中提到的相同策略，但我没有设法在这个变体上使用这些想法。

Answer 1

假设“SOME TASKS”具有恒定的时间复杂度，则复杂度确实为 O( log²𝑛 )。我们可以这样分析：

𝑖的值将是2的幂，从2⁰，2¹，2²，2³，...开始，不超过𝑛，即𝑖的最终值为2^{⌊ log₂𝑛⌋}（不大于𝑛的2的最大幂）。

内循环的迭代次数为log₂𝑖，其中𝑖取上面列出的值。这使得“某些任务”的执行总数：

      log₂2⁰ + log₂2¹ + log₂2² + ... + log₂2^{⌊log ₂𝑛⌋}

...即：

      0 + 1 + 2 + 3 + ... + ⌊log₂𝑛⌋

这是一个三角形数，因此我们得到的复杂度与最终项的平方相同：

      O(log²𝑛)