分析一个变量呈指数扩展而不是按恒定量扩展的循环

Question

我知道如果循环变量按常数指数 k 呈指数扩展，它的复杂度为 O(log(logn))。但是我无法全神贯注地分析这个函数。

void foo{
int a=0;
 for(int i=2;i<=n;i++){
   if(i%2==0){
     a++;
   } else{
     i=(i-1)*i;
   }
 }
}

I found this sequence fitting to the problem in hand

Answer 1

让我们看看 i 在循环迭代中采用的值。

在第一次迭代之前，i = 2.
在第二次迭代之前，我们有 i = 3，因为我们计算跳过“else”分支然后添加一个。
在第三次迭代之前，我们有 i = 7，因为我们计算 i = 3 * (3 - 1) 然后加一。
在第四次迭代之前，我们有 i = 43，因为我们计算 i = 7 * (7 - 1) 然后加一。
在第五次迭代之前，我们有 i = 1807，因为我们计算 i = 43 * (43 - 1) 和加一。

我只能说是一个神奇的巧合，我碰巧认出了数字序列 2、3、7、43、1807 是 Sylvester's sequence 的开始，我刚刚了解到一些几周前。检查维基百科证实，西尔维斯特的序列确实是由递推关系给出的

S₀ = 2
S_n+1 = S_n(S_n - 1) + 1 .

已知这个数列增长doubly-exponentially，S_n约等于E^2ⁿ 对于 E = 1.264084735...。所以这确实意味着该算法的迭代次数作为 n 的函数将是 O(log log n)，因为 i 快速增长 doubly-exponentially。

但假设您没有在随机维基百科搜索中找到这个确切序列的运气不佳。你还能证明运行时间是 Θ(log log n) 吗？答案是肯定的，这是一种方法。

我们可以做出的第一个观察是，与设置 i = i^{2[= 相比，此过程会导致 i 增长得更慢96=]。您可以通过查看发生了什么的相应条款来检查这一点：}

i = i(i - 1) + 1     2, 3, 7,   43, ...
i = i^2              2, 4, 16, 256, ...

如果我们以更快的速度增长 i，那么在循环的 k 次迭代之后，我们将得到 i = 2^{2^k}。（注意 2, 4, 16, 256, ... = 2^2⁰, 2^2¹, 2^2², ...)。我们停止一次 n = 2^{2^k}，这发生在 k = Θ(log log n) 次迭代之后。这提供了该算法将采取多少步的下限。

为了得到一个 upper-bound，假设我们改为初始化 i = 1.2 然后更新 i = i² 每次迭代。然后我们会得到这些数字：

i = i(i - 1) + 1       2,   3,   7,  43, ...
i = i^2              1.2, 1.4, 4.3, 18.5,

如果愿意，您可以证明，您提出的序列确实继续超过这个较小的序列。那个较小的序列有很好的属性迭代 k 上 i 的值是 (1.2)^{2^k} ，这意味着我们（再次）在 Θ(log log n) 次迭代后停止。

换句话说，我们的序列夹在两个不同的其他序列之间，每个序列都增长doubly-exponentially快，这意味着这个序列也增长doubly-exponentially快。因此，此循环在 Θ(log log n) 步后停止。

希望对您有所帮助！

分析一个变量呈指数扩展而不是按恒定量扩展的循环

Analysis of a loop that has a variable expanding exponentially not by a constant amount

algorithm

math

big-o

analysis