[理工] 台大107資演

看板Grad-ProbAsk作者 (冰淇淋)時間7年前 (2018/11/19 09:06), 編輯推噓9(9推 0噓 8→)
留言17則, 7人參與, 7年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1542589580.A.46D.html
推
11/19 12:13, 7年前 , 1F
Stack 洪逸筆記寫O(1)
11/19 12:13, 1F
→
11/19 12:14, 7年前 , 2F
Hash正常情況是O(1)沒錯 可是會因為碰撞成worst case的
11/19 12:14, 2F
→
11/19 12:14, 7年前 , 3F
話會變O(n)
11/19 12:14, 3F
推
11/19 12:22, 7年前 , 4F
第7題我會偏向有n個keys 因為是用with
11/19 12:22, 4F
推
11/19 12:29, 7年前 , 5F
Perfect hash 是沒有碰撞的喔
11/19 12:29, 5F
推
11/19 13:08, 7年前 , 6F
Stack 插入n key 不是 O(1)*n嗎
11/19 13:08, 6F
推
11/20 06:03, 7年前 , 7F
想問一下max heapify從bottom up調整各節點的話會O(
11/20 06:03, 7F
→
11/20 06:03, 7年前 , 8F
n),這樣算expected time嗎
11/20 06:03, 8F
推
11/20 17:00, 7年前 , 9F
第四題用bottom up不是O(n)嗎(不確定
11/20 17:00, 9F
→
11/20 17:29, 7年前 , 10F
st大我跟你想法一樣，只好等版友討論解答了
11/20 17:29, 10F
推
11/21 11:33, 7年前 , 11F
想問一下bucket sort是哪個呀
11/21 11:33, 11F
推
11/21 16:19, 7年前 , 12F
stack 應該是指push一個有n個keys 的stack吧
11/21 16:19, 12F
推
12/08 14:01, 7年前 , 13F
第四題B 其他一樣
12/08 14:01, 13F
→
02/03 23:32, 7年前 , 14F
關於4. 如果是初始n個元素要建一個heap累計是O(N)吧
02/03 23:32, 14F
→
02/03 23:35, 7年前 , 15F
MaxHeapify應是假設只有子樹root違反heap條件的情況
02/03 23:35, 15F
→
02/03 23:36, 7年前 , 16F
MaxHeapify本身應該是O(logN)吧(可能會跑一次樹高)
02/03 23:36, 16F
→
02/03 23:37, 7年前 , 17F
但BuildHeap只要從第N/2到1個節點做heapify 共O(N)
02/03 23:37, 17F
‣ 更多 HY0869 的文章
文章代碼(AID): #1RyWoCHj (Grad-ProbAsk)