Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

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): 自己
  • 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!

Still have questions? Get your answers by asking now.