[問題] 陣列的替代品
看板Prob_Solve (計算數學 Problem Solving)作者snobbery (egoist)時間15年前 (2009/03/17 17:10)推噓1(1推 0噓 2→)留言3則, 3人參與討論串1/1
如果我有一個n items的陣列A,
每個item都是0 ~ q之間的數值,
那可以知道要存下這個陣列要花O(n)的儲存空間,
(嚴格來說, 是log(q)*n bits)
然後每次我要查詢第i個位置的item的話, 我需要花的時間是O(1),
(反正下個A[i]的指令就馬上取到i-th item的值)
現在, 如果我想把儲存空間降到o(n),
但是也許可以允許查詢item有錯誤, 或是查詢時間可以不是constant time的話,
不知道有沒有這樣的data structure可以完成這樣的事情?
thx
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.90
→
03/18 08:29, , 1F
03/18 08:29, 1F
→
03/18 12:04, , 2F
03/18 12:04, 2F
推
03/20 20:24, , 3F
03/20 20:24, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
