algorithm - 值以 2 的幂递增的循环的时间复杂度

Question

for(i=1;i<=n;i=pow(2,i)) { print i }

这个的时间复杂度是多少？

大约 kth i 的值(value)术语将是 pow(2,(pow(2,pow(2,pow(2, pow(2,pow(2,...... k times)))))))

上面的值怎么可能，比方说kth value of i < n被解决为k .

Answer 1

你所拥有的类似于tetration(2,n)但它不是因为你得到了错误的结束条件。

复杂性在很大程度上取决于领域和实现。从您的示例代码中，我推断出真实域 和整数。

这个函数增长得非常快，所以在 5 次迭代之后你需要 bigints 甚至 +,-,*,/,<<,>>不是 O(1) . pow和print的实现也有很大的影响。

如果小n<tetration(2,4)你可以假设复杂度是O(1)因为对于这么小的 n 没有渐近可言。

注意 pow在大多数语言中是 float ，并为 2 by i 提供动力可以转化为简单的位移，所以让我们假设:

for (i=1;i<=n;i=1<<i) print(i); 

我们可以使用 i 的先前状态计算 1<<i像这样:

i0=i; i<<=(i-i0); 

但是这么大的数字没有加速。

现在十进制的复杂度print(i)是以下之一:

O( log(i))               // power of 10 datawords (like 1000000000 for 32 bit)
O((log(i))^2)            // power of 2 datawords naive print implementation
O( log(i).log(log(i)))   // power of 2 datawords subdivision or FFT based print implementation

位移的复杂度1<<i与比较i<=n是:

O(log(i))                // power of 2 datawords

因此为 print 选择最佳实现2 个数据字的幂导致迭代:

O( log(i).log(log(i) + log(i) + log(i) ) -> O(log(i).log(log(i)))

乍一看，人们会认为我们需要知道迭代次数 k来自 n :

n = tetration(2,k)
k = slog2(n)

或Knuth's notation这与Ackermann function直接相关:

n = 2↑↑k
k = 2↓↓n

但是与循环内部的东西的内部复杂性相比，迭代次数太少了，下一次迭代增长得如此之快，以至于上一次迭代与下一次迭代相比可以忽略不计，所以我们可以忽略它们，只考虑最后一次迭代/迭代...

在所有这些假设之后，我得到了最终的复杂性:

O(log(n).log(log(n)))