我如何正确计算这个时间复杂度

Question

我正在检查这段代码作为我的测试准备，但我在确定正确的时间复杂度时遇到了一些问题：

a = 1;
while (a < n) {
 b = 1;
 while (b < a^2)
  b++;
a = a*2;
}

a 的值如下：1, 2, 4, 8, ... , 2^(logn) = n

因此我们有 logn 次外循环迭代。在每个嵌套循环中，都有 a^2 次迭代，所以基本上我想出的是：

T(n) = 1 + 4 + 16 + 64 + ... + (2^logn)^2

我在查找本系列的通用术语时遇到问题，因此无法得出最终结果。（可能是因为我的计算完全不对）

非常感谢任何帮助，谢谢。

Answer 1

你的计算没问题，你对内在的分析是正确的while-loop。我们可以用一个小的 table:

来证明这一点

这基本上是一个几何级数的总和：
a1 = 1, q = 4, #n = lg n + 1

其中 #n 是元素的数量。
我们有：Sn = 1 * (4^(lgn +1) - 1)/(4-3) = (4*n^2 - 1)/3

因此我们可以说您的代码运行复杂度为 Θ(n^2)

LaTeX 中的数学解释：

How do I properly calculate this time complexity