迭代函数

Question

HW - 需要尝试复杂

time=0; 
for (i=n; i>=1; i = sqrt(i)) 
for (j=1; j<=i; j++) 
time++; 

我做了什么 - 第一圈会是这样的：我 = N，N ^（1/2）中，n ^（1/4 ）... 1 比我们得到：

n ^（1/2）^ k = 1 如果我记录双方一边得到0 ...我该怎么办？

Answer 1

我想有一个错字的地方，否则它是Θ（∞），如果输入n不小于1.（i == 1，更新i = sqrt(i)不改变i，所以这是一个无限循环）。

因此，让我们假设它实际上

time = 0; 
for (i = n; i > 1; i = sqrt(i)) 
    for (j = 1; j <= i; j++) 
     time++; 

然后，为了获得嵌套循环的复杂性，你需要总结的内循环的复杂性外循环的每个迭代。在这里，内部循环显然运行了i次，所以我们需要总结外部循环中运行的值i。这些值是n, n^0.5, n^0.25, ..., n^(1/2^k)，其中k的特征在于

n^(1/2^(k+1)) < 2 <= n^(1/2^k) 

或，等价地，

2^(2^k) <= n < 2^(2^(k+1)) 
2^k <= lg n < 2^(k+1) 
k <= lg (lg n) < k+1 
k = floor(lg(lg n)) 

现在它仍然是从上方和下方估计的总和，以获得算法的Θ。如果您开始记下一些（大）值为n的总和，这个估计值非常容易。