algorithm - 确定简单循环的 O-runtime

Question

我在伪代码中有这个简单的循环:

i = 2

while i < n do
    i = i * i

关于 n，我如何确定该算法的 Big-O？

在这种情况下，i 将变为:2、4、16、256、65536 等，每次 i 本身都是平方的。我不确定如何想出一个表达来描述这一点。

Answer 1

乍一看，时间复杂度是 O(log(n))，因为 n 在 而 是静态的情况下。但是，如果仔细检查，您会发现紧束缚。要按照以下步骤执行此操作，它们是 2^(2^k)。例如对于 k = 0, 1, 2, ... 你可以看到 i 是增长 2, 4, 16, 246, ...。因此，确切的复杂度是 O(log(log(n)))。