## Trending News

# 請教一個時間複雜度(time complexity)問題?

這是98年高中資訊學科能力測驗第17題題目。

程式碼

i=2

x=0

while i <= n do

{

i = i ^ 2

x = x + 1

}

正確解答時間複雜度是O(Log2(Log2n)) 註:2指以2為底。

一直百思不解，為什麼不是O(Log2n) 註:2指以2為底。

如願意解說者請詳細些，因本人悟性不高~哈 ^_^

感謝賜教!!

### 2 Answers

- -Aleck-Lv 51 decade agoFavorite Answer
不曉得你是不是看錯題目? i=i^2應該是指i=i*i吧?

i=i*2才是O(logn)

i=i^i就會變成O(log(logn))

根據迴圈條件i值會等於:

i=2^2^X

所以X=log(logi)

故time complexity=O(log(logn))

註:以2為底

Source(s): 自己- Login to reply the answers

- NelsonLv 51 decade ago
(i^2)^2...)^2 > n, and

we can see that x increases 1 in every single cycle

=> i^(2^x) > n

=> (2^x)log i > log n

∵ i=2

=> x > log log n

And we can also have x-1 < log log n, in the same way

=> O(x) = O(x) - O(1) = log log n

2010-02-23 21:15:10 補充：

ouh, I didn't take the self multiplication into account. Even using fast Fourier I can only give out a very bad bound: (log n)((log log n)^2). The actual bound must be much lower.

2010-02-23 21:15:13 補充：

But this quite goes beyond the scope of high school students' understanding, so... I guess we can leave it as it is, problem solved, yeh!

- Login to reply the answers