迭代函數

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的總和，這個估計值非常容易。