algorithm - 了解循环变量在呈指数增长时所取的值

Question

我知道循环变量呈指数增长的循环的时间复杂度是 O(log(log(n)))。

在下面的代码中，我取值 2, 2^k, (2^k)^k = 2^k^2, (2^k^2)^k = 2^k^3, …, 2 ^k^logk(日志(n))。最后一项必须小于或等于 n，我们有 2^k^logk(log(n)) = 2^log(n) = n。

for (int i = 2; i <=n; i = pow(i, k))  
{
    // some O(1) expressions or statements
} 

我不明白 i 的最终值是如何变成 2^k^logk(log(n)) 的？序列如何从数学上得到这个一般值？

Answer 1

首先让我们修改代码以使用另一个变量 j 显式跟踪迭代次数:

for (int i = 2, j=0; i <=n; j+=1, i = pow(i, k))  

我们还假设在某些步骤中，条件 i 正好等于 n。那将是最后一次迭代。在那一步 j 的值是多少？

我们可以看到在迭代过程中 i 总是

i = 2^(k^j)

所以在那一步

n = 2^(k^j)

要从中得到 j 让我们首先将 log2 应用到两边:

log2(n) = k^j

然后将 logk(即以 k 为基数的 log)应用到两侧:

j = logk(log2(n))

显然，完全匹配 i == n 是一种罕见的情况，但它的缺失只会影响 1 的迭代总数，而不会影响 big-O。换句话说，i 的最后一个值不会完全变成 2^(k^logk(log2(n))) 即 n。它变得像 2^(k^logk(floor(log2(n)))) 但渐近地它是同一件事。