計算時間複雜度

Question

有人可以用下面的代碼的時間複雜度幫助：

for(i = 0; i <= n; i++) 
{ 
    for(j = 0; j <= i; j++) 
     { 
     for(k = 2; k <= n; k = k^2) 
       print("") 
     } 

的A/C給我的第一個循環運行N次，第2次會爲（1 + 2 + 3上運行。 ..n）倍，第三次loglogn次.. 但我不知道答案。

Answer 1

我們從內部開始工作。考慮最內層循環：

for(k = 2; k <= n; k = k^2) 
    print("") 

print("")執行多少次迭代？首先請注意n是恆定的。 k假定什麼序列值？

iter | k 
-------- 
    1 | 2 
    2 | 4 
    3 | 16 
    4 | 256 

我們可能會在幾個方面找到這方面的公式。我用猜測和證明得到iter = log(log(k)) + 1。由於如果該值已經大於n，則循環將不會執行下一次迭代，因此爲n執行的迭代總數爲floor(log(log(n)) + 1)。我們可以用幾個值來檢查這個值，以確保我們得到了正確的結果。對於n = 2，我們得到一個正確的迭代。對於n = 5，我們得到兩個。等等。

下一級確實是i + 1迭代，其中i從0變化到n。因此，我們必須計算總和1, 2, ..., n + 1，這將給我們最外層和中層循環的總迭代次數：這個總和是(n + 1)(n + 2)/2我們必須乘以內層循環的代價才能得到答案(n + 1)(n + 2)(log(log(n)) + 1)/2以獲得總成本的片段。擴展中增長最快的術語是n^2 log(log(n))，所以這通常是漸近複雜性。