[理工] 成大 資結 100

看板Grad-ProbAsk作者 (NONO)時間14年前 (2011/12/04 23:18), 編輯推噓5(5推 0噓 13→)
留言18則, 4人參與, 最新討論串1/1
成大資結 100年 題目:http://ppt.cc/dc4e 共有三個問題 1)1-4小題 題目是T or F 我的書上沒有針對 hash 的時間複雜度討論 所以想問一下 答案是多少 另外 hash的Big O 會因為資料量 和fuchion 而改變嗎? 2)為類題敘述 我想問的是 他到底是要考單選還是複選呢 裡面敘述有說 如果覺得是多個就選多個 但是整張考券後面又有所謂的"多選題" 所以... 搞不太懂 請各位高手幫忙 不然真的不知道該怎樣寫 3)2-8 類題屬於 上一題問的 答案是多少呢? 感謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.134.26.47
推
12/04 23:21, , 1F
單複選~ is/are 很賊= = +
12/04 23:21, 1F
→
12/04 23:31, , 2F
我個人是覺得T HASH最糟糕就O(n)吧
12/04 23:31, 2F
→
12/04 23:35, , 3F
如果hash 取 mod 值為資料量最大 = n 那就是 O(n)
12/04 23:35, 3F
→
12/04 23:36, , 4F
worst case↑
12/04 23:36, 4F
→
12/05 00:39, , 5F
我是認為hashing n個bucket n個item,若是除了第一個沒有
12/05 00:39, 5F
→
12/05 00:40, , 6F
collision,剩下n-1個都與第一個發生collision
12/05 00:40, 6F
→
12/05 00:42, , 7F
若是linear probing的話,第一個collision為1到第n-1個為n-1
12/05 00:42, 7F
→
12/05 00:43, , 8F
樓上 那time complexity 仍是 O(n) 吧?
12/05 00:43, 8F
→
12/05 00:44, , 9F
平均collision為 (n*(n-1))/n,總共n item=>O(n^2)
12/05 00:44, 9F
→
12/05 00:51, , 10F
2-8 我選.....C
12/05 00:51, 10F
→
12/05 00:54, , 11F
D一直很想選 因為我找不到反例
12/05 00:54, 11F
→
12/05 00:56, , 12F
但若是用best 去跟failure search比的話又很容易比的出來
12/05 00:56, 12F
推
12/05 09:16, , 13F
C不是有說，data no sorted，那binary search還會比seque
12/05 09:16, 13F
→
12/05 09:16, , 14F
ntial search來的快嗎@@?
12/05 09:16, 14F
推
12/05 10:33, , 15F
想想好像是不會，我重看一下題目=.=
12/05 10:33, 15F
推
12/05 10:49, , 16F
看來這題我無法回答了，交給其它高手(T_T)
12/05 10:49, 16F
推
12/05 10:53, , 17F
題目都沒說是best or avg or worst那我猜e(T_T)
12/05 10:53, 17F
→
09/11 14:38, , 18F
09/11 14:38, 18F
‣ 更多 showyoulovex 的文章
文章代碼(AID): #1EsuzJ3I (Grad-ProbAsk)