[理工] 成大 資結 100

[showyoulovex (NONO)]

成大資結 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
推 SiriusCloud:單複選~ is/are 很賊= = +
→ SiriusCloud:我個人是覺得T HASH最糟糕就O(n)吧
→ SiriusCloud:如果hash 取 mod 值為資料量最大 = n 那就是 O(n)
→ SiriusCloud:                           worst case↑
→ gskman:我是認為hashing n個bucket n個item,若是除了第一個沒有
→ gskman:collision,剩下n-1個都與第一個發生collision
→ gskman:若是linear probing的話,第一個collision為1到第n-1個為n-1
→ SiriusCloud:樓上  那time complexity 仍是 O(n) 吧?
→ gskman:平均collision為 (n*(n-1))/n,總共n item=>O(n^2)
→ gskman:2-8 我選.....C
→ gskman:D一直很想選 因為我找不到反例
→ gskman:但若是用best 去跟failure search比的話又很容易比的出來
推 kiwidoit:C不是有說，data no sorted，那binary search還會比seque
→ kiwidoit:ntial search來的快嗎@@?
推 gskman:想想好像是不會，我重看一下題目=.=
推 gskman:看來這題我無法回答了，交給其它高手(T_T)
推 gskman:題目都沒說是best or avg or worst那我猜e(T_T)
→ sneak:             https://daxiv.com