作者HY0869 (冰淇淋)
看板Grad-ProbAsk
標題[理工] 台大107資演
時間Mon Nov 19 09:06:17 2018
https://i.imgur.com/OnM5vLi.jpg
想確定一下答案是
E
D
B
D
B
A
C
嗎
順便問一下第7題是插入n個key還是插入有n個key的樹
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.247.245
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1542589580.A.46D.html
1F：推 zuchang: Stack 洪逸筆記寫O(1) 11/19 12:13
2F：→ zuchang: Hash正常情況是O(1)沒錯 可是會因為碰撞成worst case的 11/19 12:14
3F：→ zuchang: 話會變O(n) 11/19 12:14
4F：推 zuchang: 第7題我會偏向有n個keys 因為是用with 11/19 12:22
5F：推 kobebset105: Perfect hash 是沒有碰撞的喔 11/19 12:29
6F：推 kobebset105: Stack 插入n key 不是 O(1)*n嗎 11/19 13:08
7F：推 kcilao110779: 想問一下max heapify從bottom up調整各節點的話會O( 11/20 06:03
8F：→ kcilao110779: n),這樣算expected time嗎 11/20 06:03
9F：推 st945712: 第四題用bottom up不是O(n)嗎(不確定 11/20 17:00
10F：→ kcilao110779: st大我跟你想法一樣，只好等版友討論解答了 11/20 17:29
11F：推 kuan0908: 想問一下bucket sort是哪個呀 11/21 11:33
12F：推 zuchang: stack 應該是指push一個有n個keys 的stack吧 11/21 16:19
13F：推 QQStanGD666: 第四題B 其他一樣 12/08 14:01
14F：→ GeniusPuddin: 關於4. 如果是初始n個元素要建一個heap累計是O(N)吧 02/03 23:32
15F：→ GeniusPuddin: MaxHeapify應是假設只有子樹root違反heap條件的情況 02/03 23:35
16F：→ GeniusPuddin: MaxHeapify本身應該是O(logN)吧(可能會跑一次樹高) 02/03 23:36
17F：→ GeniusPuddin: 但BuildHeap只要從第N/2到1個節點做heapify 共O(N) 02/03 23:37