作者gcobs0834 (gcobs0834)
看板Grad-ProbAsk
標題[理工] 107台大資演(I)
時間Fri Feb 15 16:12:44 2019
不好意思我覺得我這應該是英文問題
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550218367.A.EC2.html
1F：→ DLHZ: key是指經過hadh function拿來對table位子的那個值 應該是O( 02/15 16:36
2F：→ DLHZ: N) Insert/Delete on (red-black tree with N keys) 應該是O 02/15 16:36
3F：→ DLHZ: (lgn) 02/15 16:36
4F：→ DLHZ: 給你插也要知道樹的大小 所以應該是指大小沒錯 啊key就是那 02/15 16:41
5F：→ DLHZ: 個意思了 應該是沒問題 02/15 16:42
6F：推 eric131204: 所以hash那題是search n個key 每個O(1)嗎 02/15 16:45
7F：→ DLHZ: 有提到perfect hashing所以search一次應該是O(1) 02/15 16:52
8F：→ DLHZ: 就是你講的那樣 02/15 16:53
9F：推 eric131204: 那static key是什麼意思，key不能視為hash table上的s 02/15 17:03
10F：→ eric131204: lot index嗎？畢竟其他題他都是類似的說法（stack of 02/15 17:03
11F：→ eric131204: n keys, tree with n keys)之類的？ 02/15 17:03
12F：→ gcobs0834: 所以這兩題的n都是題目的大小 而不是做動作的次數對吧 02/15 17:05
13F：→ gcobs0834: ？ 02/15 17:05
14F：推 eric131204: 照D大說的hash那題是做n次吧？ 02/15 17:06
16F：→ GeniusPuddin: shing 02/15 17:31
17F：→ GeniusPuddin: 照維基看起來是有分動態跟靜態兩種hashing? 02/15 17:32
18F：→ GeniusPuddin: 所以應該是指N格靜態的hashtable做一次搜尋? 02/15 17:33
19F：推 eric131204: 疑 所以還是O(1)嗎 搞混了 02/15 19:08
20F：→ gcobs0834: 我一開始看題目覺得是做n次啦 但我覺得他給的其實是資 02/15 22:09
21F：→ gcobs0834: 料大小是n 02/15 22:09
22F：→ aggress5566: 如果是(key, data) 那N個key應該是所謂N個slot 02/15 22:19