Research Space for Linear Algebra & Discrete Mathematics
1. 首先觀察最外圍的迴圈總共會執行 lg(n) 次,當 a=1 時, 裡面會執行 1 次當 a=2^1 時, 裡面會執行 2^1 次當 a=2^2 時, 裡面會執行 2^2 次...當 a=2^lgn 時, 裡面會執行 2^lgn 次所以 time complexity 為 2^0 + 2^1 + ... + 2^lgn = 2^(lgn+1)-1 = 2n-1 = O(n)2. 當 a=1 時, 裡面會執行 1 次當 a=2^1 時, 裡面會執行 2 次當 a=2^2 時, 裡面會執行 3 次...當 a=2^lgn 時, 裡面會執行 lgn+1 次所以複雜度為 1+2+...+(lgn+1)= (lgn+2)(lgn+1)/2 = O((lgn)^2)
感謝助教的解答, 但是我也是這樣解, 可是答案和網站上公佈的不一樣, 這是資料結構的第一題, 第一小題是logn*logn, 第二小題是logn*loglogn怪怪的
我怎記得我去看解答 解答寫說第一題送分XD
...我是在網站上看的pdf檔, 沒看到送分耶?所以答案有錯囉?
http://www.growth.com.tw/groeth_web/2011school_test/images/2011台北碩士龍門資工所模考-軟體設計解答.pdf<< 模擬考解答
那應該是公佈的解答有誤, 這樣解沒問題的坐在電腦前有個好處就是, 你可以將那幾行包成小程式來實際模擬一下, 在看到print出來的結果和你的想法一致時你就會完全放心了
謝謝助教和allen的幫忙…還好沒花太多時間去解~~真是…
張貼留言
7 則留言:
1. 首先觀察最外圍的迴圈總共會執行 lg(n) 次,
當 a=1 時, 裡面會執行 1 次
當 a=2^1 時, 裡面會執行 2^1 次
當 a=2^2 時, 裡面會執行 2^2 次
...
當 a=2^lgn 時, 裡面會執行 2^lgn 次
所以 time complexity 為
2^0 + 2^1 + ... + 2^lgn
= 2^(lgn+1)-1 = 2n-1 = O(n)
2.
當 a=1 時, 裡面會執行 1 次
當 a=2^1 時, 裡面會執行 2 次
當 a=2^2 時, 裡面會執行 3 次
...
當 a=2^lgn 時, 裡面會執行 lgn+1 次
所以複雜度為 1+2+...+(lgn+1)
= (lgn+2)(lgn+1)/2 = O((lgn)^2)
感謝助教的解答, 但是我也是這樣解, 可是答案和網站上公佈的不一樣, 這是資料結構的第一題, 第一小題是logn*logn, 第二小題是logn*loglogn怪怪的
我怎記得我去看解答 解答寫說第一題送分XD
...我是在網站上看的pdf檔, 沒看到送分耶?所以答案有錯囉?
http://www.growth.com.tw/groeth_web/2011school_test/images/2011台北碩士龍門資工所模考-軟體設計解答.pdf
<< 模擬考解答
那應該是公佈的解答有誤, 這樣解沒問題的
坐在電腦前有個好處就是, 你可以將那幾行包成小程式來實際模擬一下, 在看到print出來的結果和你的想法一致時你就會完全放心了
謝謝助教和allen的幫忙…還好沒花太多時間去解~~真是…
張貼留言