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

看板Grad-ProbAsk作者 (gcobs0834)時間6年前 (2019/02/15 16:12), 編輯推噓4(4推 0噓 18→)
留言22則, 5人參與, 6年前最新討論串1/1
不好意思我覺得我這應該是英文問題 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
→
02/15 16:36, 6年前 , 1F
key是指經過hadh function拿來對table位子的那個值 應該是O(
02/15 16:36, 1F
→
02/15 16:36, 6年前 , 2F
N) Insert/Delete on (red-black tree with N keys) 應該是O
02/15 16:36, 2F
→
02/15 16:36, 6年前 , 3F
(lgn)
02/15 16:36, 3F
→
02/15 16:41, 6年前 , 4F
給你插也要知道樹的大小 所以應該是指大小沒錯 啊key就是那
02/15 16:41, 4F
→
02/15 16:42, 6年前 , 5F
個意思了 應該是沒問題
02/15 16:42, 5F
推
02/15 16:45, 6年前 , 6F
所以hash那題是search n個key 每個O(1)嗎
02/15 16:45, 6F
→
02/15 16:52, 6年前 , 7F
有提到perfect hashing所以search一次應該是O(1)
02/15 16:52, 7F
→
02/15 16:53, 6年前 , 8F
就是你講的那樣
02/15 16:53, 8F
推
02/15 17:03, 6年前 , 9F
那static key是什麼意思，key不能視為hash table上的s
02/15 17:03, 9F
→
02/15 17:03, 6年前 , 10F
lot index嗎？畢竟其他題他都是類似的說法（stack of
02/15 17:03, 10F
→
02/15 17:03, 6年前 , 11F
n keys, tree with n keys)之類的？
02/15 17:03, 11F
→
02/15 17:05, 6年前 , 12F
所以這兩題的n都是題目的大小 而不是做動作的次數對吧
02/15 17:05, 12F
→
02/15 17:05, 6年前 , 13F
？
02/15 17:05, 13F
推
02/15 17:06, 6年前 , 14F
照D大說的hash那題是做n次吧？
02/15 17:06, 14F
→
02/15 17:30, 6年前 , 15F
02/15 17:30, 15F
→
02/15 17:31, 6年前 , 16F
shing
02/15 17:31, 16F
→
02/15 17:32, 6年前 , 17F
照維基看起來是有分動態跟靜態兩種hashing?
02/15 17:32, 17F
→
02/15 17:33, 6年前 , 18F
所以應該是指N格靜態的hashtable做一次搜尋?
02/15 17:33, 18F
推
02/15 19:08, 6年前 , 19F
疑 所以還是O(1)嗎 搞混了
02/15 19:08, 19F
→
02/15 22:09, 6年前 , 20F
我一開始看題目覺得是做n次啦 但我覺得他給的其實是資
02/15 22:09, 20F
→
02/15 22:09, 6年前 , 21F
料大小是n
02/15 22:09, 21F
→
02/15 22:19, 6年前 , 22F
如果是(key, data) 那N個key應該是所謂N個slot
02/15 22:19, 22F
‣ 更多 gcobs0834 的文章
文章代碼(AID): #1SPdH_x2 (Grad-ProbAsk)