這個循環的時間複雜度

Question

for (int i=0; i<n; i++) 
{ 
int j = 2; 
while (j<i) 
    j = j * j; 
} 

我認爲它的n * log（n）作爲第一個循環重複n次，但我不確定第二個。

Answer 1

由於這個問題具有作業的所有特徵，我不會直接給出最終答案，而是給你一些關於如何到達那裏的指導。

你說得對，你需要一個內部循環迭代次數的界限來確定整體界限。爲了評估這一點，考慮值j將採用該循環的連續迭代形式：2,4,16,256等。根據循環迭代次數爲該數字編寫閉合公式是有用的。

很明顯，序列由增加2的冪組成，但不是線性增加冪。我們有2 ，2 ，2 ，2 ，......在這一點上，雖然，你應該認識到模式，並能編寫公式的值j內環的k次迭代之後，對ķ = 0，1，2，3 ....讓內（ķ）指定該公式。 （具體公式留作練習。）

那麼對於給定的值i，該內循環將執行多少次迭代？可變j需要的內（ķ）作爲循環迭代的值，並且在循環終止時j >= i，因此迭代次數是最少值ķ使得內（ķ）是在至少一樣大i，而循環的迭代的最大數目是最少ķ使得內（ķ）是至少n。現在，估計n爲內部（k），並且解決了k。

剩下的細節再次留作練習。