Re: [理工] 100&101台大電機丙-DS

[tzutengweng (神奇的湯姆)]

※ 引述《BuliBuchi (不離不棄)》之銘言：
: http://tinyurl.com/cpkzwuq 101
: http://tinyurl.com/cd77xza 100
: 想跟大家對個答案
: 不過寫起來蠻不順的
: 所以有錯請大大指教
: 101
: 單選
: 1~5.AECBD
: 多選
: 6.AD
: 7.CDE
: 8.AB
: 9.ADE
: 10.CDE
: 11.AB


101第三題  我覺得是D

外面的for loop O(n)

內層

i=0
goo(0)

i=1
goo(1)
goo(0)

O(1)+O(0)=O(1)

i=2
goo(2)
goo(1)
goo(0)

O(2)+O(1)+O(0)=O(1)


....

i=n-1
goo(n-1)
goo((n-1)/2)
..
goo(1)
goo(0)
i=n-1時，有lgn個goo(i)
time complexity: O(nlgn)

所以inner loop是O(1)+O(1)+....+O(nlgn)=O(nlgn)

內外總共O(n)xO(nlgn)=O(n^2lgn)


101第七題  我覺得B是對的

doubly linked list刪除中間的node   要先找到中間的node才能刪

找的過程需要O(n)  刪除要O(1)

所以一共是O(n)   即使他已經排好也是一樣


第9題

我用https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

insert(10, 28, 32, 37, 44, 46, 50)

模擬  E是錯的




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.241.194
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483841003.A.BD1.html
※ 編輯: tzutengweng (36.230.241.194), 01/08/2017 10:12:11
推 Transfat: 101第七題，可是已經sorted好了，即使你要找到第k個，要
→ Transfat: sequential search的時間也頂多是O(k), 移除linked時間
→ Transfat: 是O(1), 也不會到O(n)吧
※ 編輯: tzutengweng (36.230.241.194), 01/08/2017 11:10:05
推 moooner: 第三題也有疑問，我也算出n^2lgn，為何可以到n^2？
推 yupog2003: 第三題我算n^2  http://imgur.com/zDFGzNj
推 Transfat: 第九題我覺得沒E
→ yupog2003: 原po是錯在i=n-1時，有lgn個goo("j")才對，注意j是會
→ yupog2003: 越來越小的，直接用i的話會多算
→ yupog2003: 話說第三題應該是無限迴圈才對，因為
→ yupog2003: for (j=i;j>=0;j=j/2)，就算j除到0了還是不會停止，
→ yupog2003: 會一直做下去無法terminate...