John
Lv 4
John asked in 電腦與網際網路程式設計 · 1 decade ago

請教一個時間複雜度(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

Rating
  • 1 decade ago
    Favorite 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
  • Nelson
    Lv 5
    1 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
Still have questions? Get your answers by asking now.