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

[odanaga (PixiyON)]

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
推 JackLeeing: 18) 你拿{1,2,3,4,5,6,7}Run一次看看
→ JackLeeing: 等等這不行~~
QQ
推 tedchang102: 第三題，每次排序完皆要輸出一次n元串列，為n*n!
ok
推 tedchang102: 第八題如果考在演算法樹高應是從0起算
看作log(n-1) n=1->log0 是負無限大
看作logn-1   n=1->-1   應該沒有-1高度吧
推 JackLeeing: 2-3-4 tree:insert 1 to 10 接著刪除 10 9 8 高度3
→ JackLeeing: 2-3 tree:insert 1 2 3 5 6 4 7 高度2
→ JackLeeing: 這樣就錯囉
我發現我好像不會B樹插入刪除 QQ (只會234樹插入)
不過我有新的想法  反正我隨便建只要符合定義都OK(不管插入刪除順序)
那7個node確實可能2-3-4高過2-3 (大概吧)
QQ
推 tedchang102:  最後一題這樣証不知對不對
→ tedchang102:  http://i.imgur.com/mj3604H.jpg
→ tedchang102:  http://i.imgur.com/JQNBye2.jpg
窩幫你改一下次序
除了敘述好像有點怪以外應該可以 (大概吧)
就是234tree只用2-node建 會比23tree全用3-node建來得高
推 goldflower: 一看才發現我完全忘記2-3-4tree在幹嘛了...崩潰QQ
沒關西台聯大combo還有70天台大還有90天
※ 編輯: odanaga (219.71.20.153), 11/19/2015 23:54:00
推 goldflower: 1應該就是他忘記說他排序好吧...
→ goldflower: http://bigocheatsheet.com