[理工] DS考古 台大電機丙102

看板Grad-ProbAsk作者 (PixiyON)時間10年前 (2015/11/19 22:19), 10年前編輯推噓7(7推 0噓 6→)
留言13則, 3人參與, 最新討論串1/1
http://i.imgur.com/fBak8EA.png
1. 給的答案是O 不過陣列不是要排序過才能有O(logn)的搜索複雜度? 3. 答案給的是O 我自己是覺得是θ(n!) 不知道有沒有哪裡想錯 http://i.imgur.com/57tsL8R.png
8. 給的答案給O 不過這帶1進去不就錯了嗎? http://i.imgur.com/j5WOwJu.png
18.給的答案是X 直觀認為是對的 想知道為什麼錯 (或是能證明為什麼對也可以QQ) 以上 希望各位大大幫DS渣 QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.71.20.153 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1447942748.A.CEA.html
推
11/19 22:34, , 1F
18) 你拿{1,2,3,4,5,6,7}Run一次看看
11/19 22:34, 1F
→
11/19 22:35, , 2F
等等這不行~~
11/19 22:35, 2F
QQ
推
11/19 22:48, , 3F
第三題，每次排序完皆要輸出一次n元串列，為n*n!
11/19 22:48, 3F
ok
推
11/19 22:53, , 4F
第八題如果考在演算法樹高應是從0起算
11/19 22:53, 4F
看作log(n-1) n=1->log0 是負無限大 看作logn-1 n=1->-1 應該沒有-1高度吧
推
11/19 23:11, , 5F
2-3-4 tree:insert 1 to 10 接著刪除 10 9 8 高度3
11/19 23:11, 5F
→
11/19 23:12, , 6F
2-3 tree:insert 1 2 3 5 6 4 7 高度2
11/19 23:12, 6F
→
11/19 23:12, , 7F
這樣就錯囉
11/19 23:12, 7F
我發現我好像不會B樹插入刪除 QQ (只會234樹插入) 不過我有新的想法 反正我隨便建只要符合定義都OK(不管插入刪除順序) 那7個node確實可能2-3-4高過2-3 (大概吧) QQ
推
11/19 23:35, , 8F
最後一題這樣証不知對不對
11/19 23:35, 8F
→
11/19 23:35, , 9F
11/19 23:35, 9F
→
11/19 23:35, , 10F
11/19 23:35, 10F
窩幫你改一下次序 除了敘述好像有點怪以外應該可以 (大概吧) 就是234tree只用2-node建 會比23tree全用3-node建來得高
推
11/19 23:49, , 11F
一看才發現我完全忘記2-3-4tree在幹嘛了...崩潰QQ
11/19 23:49, 11F
沒關西台聯大combo還有70天台大還有90天 ※ 編輯: odanaga (219.71.20.153), 11/19/2015 23:54:00
推
11/19 23:58, , 12F
1應該就是他忘記說他排序好吧...
11/19 23:58, 12F
→
11/19 23:58, , 13F
11/19 23:58, 13F
‣ 更多 odanaga 的文章
文章代碼(AID): #1MJTfSpg (Grad-ProbAsk)