[理工] 103成大 程式設計

看板Grad-ProbAsk作者 (hikke)時間7年前 (2019/01/19 23:04), 編輯推噓5(5推 0噓 15→)
留言20則, 5人參與, 7年前最新討論串1/1
https://i.imgur.com/VwTE6qR.jpg
小弟要問一下是非第三題的答案 我不是很確定worst case用chain能不能到O(log n) https://i.imgur.com/q2m1gHX.jpg
演算法是非2、3小題 不確定答案 我都不知道怎麼解釋 第3小題之前板上有 只是我不太懂 還有第二大題 他有兩個條件 這要怎麼去算他的時間複雜度啊 謝謝各位大大 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.14.160 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1547910299.A.738.html
推
01/19 23:48, 7年前 , 1F
1.3 F 如果每個數都對應到同一格 這樣chain長度為n 最長
01/19 23:48, 1F
→
01/19 23:48, 7年前 , 2F
搜尋時間為O(n)
01/19 23:48, 2F
推
01/19 23:52, 7年前 , 3F
演算法1.2 如果是skew-tree 需要O(n) 可以畫圖實作看看
01/19 23:52, 3F
→
01/20 00:22, 7年前 , 4F
演算法1.3 merge A1A2A3成一個sort list需要O(n+n+n)=O(
01/20 00:22, 4F
→
01/20 00:22, 7年前 , 5F
n) 因為是balance bst 所以root需為中間值 在list找到中
01/20 00:22, 5F
→
01/20 00:22, 7年前 , 6F
間值的時間為O(1) 用遞迴概念 T(n)=2T(n/2)+O(1)=O(n)
01/20 00:22, 6F
→
01/20 00:22, 7年前 , 7F
兩者相加為O(n)
01/20 00:22, 7F
→
01/20 00:38, 7年前 , 8F
想問ㄧ下第三題 如果list用AVL tree去maintain的話
01/20 00:38, 8F
→
01/20 00:39, 7年前 , 9F
不是可以達到O(logn)嗎?
01/20 00:39, 9F
→
01/20 00:46, 7年前 , 10F
logn是單項操作的時間吧 要再乘上n 因為題目給的是low b
01/20 00:46, 10F
→
01/20 00:46, 7年前 , 11F
ound 但有辦法在小於O(nlogn)的時間求出
01/20 00:46, 11F
→
01/20 00:48, 7年前 , 12F
所以答案是F
01/20 00:48, 12F
→
01/20 01:09, 7年前 , 13F
我說的是DS Hash 那題
01/20 01:09, 13F
推
01/20 01:15, 7年前 , 14F
Chaining mouther是以link list的方式去串聯同一格的值
01/20 01:15, 14F
→
01/20 01:15, 7年前 , 15F
搜尋時間比照link list
01/20 01:15, 15F
→
01/20 01:15, 7年前 , 16F
是chaining method...選錯字
01/20 01:15, 16F
推
01/20 09:26, 7年前 , 17F
01/20 09:26, 17F
推
01/20 10:12, 7年前 , 18F
想同問M是什麼?? 常數嗎??
01/20 10:12, 18F
→
01/20 11:24, 7年前 , 19F
感謝大大們
01/20 11:24, 19F
→
01/20 14:18, 7年前 , 20F
關於那個M 台大考過類似題 是當變數來看
01/20 14:18, 20F
‣ 更多 st474ddr 的文章
文章代碼(AID): #1SGpoRSu (Grad-ProbAsk)