作者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/cn.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