Re: [理工] 100&101台大電機丙-DS
※ 引述《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
推
01/08 11:07, , 1F
01/08 11:07, 1F
→
01/08 11:07, , 2F
01/08 11:07, 2F
→
01/08 11:07, , 3F
01/08 11:07, 3F
※ 編輯: tzutengweng (36.230.241.194), 01/08/2017 11:10:05
推
01/08 11:17, , 4F
01/08 11:17, 4F
推
01/08 11:52, , 5F
01/08 11:52, 5F
推
01/08 11:55, , 6F
01/08 11:55, 6F
→
01/08 11:58, , 7F
01/08 11:58, 7F
→
01/08 11:58, , 8F
01/08 11:58, 8F
→
01/08 15:54, , 9F
01/08 15:54, 9F
→
01/08 15:55, , 10F
01/08 15:55, 10F
→
01/08 15:55, , 11F
01/08 15:55, 11F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 17 之 19 篇)：