这个依赖 for 循环的复杂性是多少，两者都通过乘法递增？

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,…,nO(logu2061i)

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

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

最终答案

这段代码的总时间复杂度是： O((logu2061n)^2)

我遵循了这里提到的相同策略。但很难将想法融合在一起。

Answer 1

假设“某些任务”具有恒定的时间复杂度，那么您从法学硕士那里得到的答案是正确的。我们可以这样分析：

𝑖的值将是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²𝑛)