與一立方迭代

Question

我試圖分析以下算法的時間複雜度while循環時間複雜度分析：

Algorithm WhileLoop2(n): 
    x = 0 
    j = 3 
    while(j <= n) 
     x = x + 1 
     j = j * j * j 
    return x 

我認爲，而它的循環，J會3J，9J，27J， ......但我不確定會有多大的複雜性。我聽說它是​​O（loglogn），但我不知道如何檢查它或如何達到這一點。任何幫助將不勝感激。

Answer 1

只要條件滿足，算法就會重複：j <= n。所以當它停止時j > n。所以它會與迭代j =

• 27（3^3）
• 19683（27^3 = 3 ^（3^3））
• ...

所以最後的j等於3^(3^i)其中i是迭代計數。因此，當算法停止時，我們得到：3^3^i > n。從log(3)雙方我們得到：3^i > log(3)(n)。再次拿到log(3)，我們得到：i > log(3)(log(3)(n))。所以確實是O(loglogn)。