[理工] 107台大資演(I)

[gcobs0834 (gcobs0834)]

不好意思我覺得我這應該是英文問題

search on hash table with N static keys and perfect hashing
這句話的意思應該是在hash table裡 找n個數還是在這n格裡面做search呢 一個O(1)一個O(N)?

Insert/Delete on red-black tree with N keys
跟上面的問題應該是一樣的
O(lgN)或O(nlgN)?

簡單請教

-----
Sent from JPTT on my Asus ASUS_X00QD.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.20.235
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550218367.A.EC2.html
→ DLHZ: key是指經過hadh function拿來對table位子的那個值 應該是O(
→ DLHZ: N) Insert/Delete on (red-black tree with N keys) 應該是O
→ DLHZ: (lgn)
→ DLHZ: 給你插也要知道樹的大小 所以應該是指大小沒錯 啊key就是那
→ DLHZ: 個意思了 應該是沒問題
推 eric131204: 所以hash那題是search n個key 每個O(1)嗎
→ DLHZ: 有提到perfect hashing所以search一次應該是O(1)
→ DLHZ: 就是你講的那樣
推 eric131204: 那static key是什麼意思，key不能視為hash table上的s
→ eric131204: lot index嗎？畢竟其他題他都是類似的說法（stack of
→ eric131204:  n keys, tree with n keys)之類的？
→ gcobs0834: 所以這兩題的n都是題目的大小 而不是做動作的次數對吧
→ gcobs0834: ？
推 eric131204: 照D大說的hash那題是做n次吧？
→ GeniusPuddin: https://en.wikipedia.org/wiki/Dynamic_perfect_ha
→ GeniusPuddin: shing
→ GeniusPuddin: 照維基看起來是有分動態跟靜態兩種hashing?
→ GeniusPuddin: 所以應該是指N格靜態的hashtable做一次搜尋?
推 eric131204: 疑 所以還是O(1)嗎 搞混了
→ gcobs0834: 我一開始看題目覺得是做n次啦 但我覺得他給的其實是資
→ gcobs0834: 料大小是n
→ aggress5566: 如果是(key, data) 那N個key應該是所謂N個slot