[問題] 陣列的替代品

[snobbery (egoist)]

如果我有一個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
推 TroyLee:log(q) 已經是常數不是嗎?
→ snobbery:但是log(q)*n仍然是O(n)啊~
推 Huangs:如果 q < n 那用 counting sort 的方式來存
推 ksmrt0123:既然允許查詢item有錯誤, 那都回0吧... constant time!
→ ksmrt0123:且不需什麼 data structure
推 ledia:壓縮 / 解壓縮呢 ? 如果允許存一個 fix size lookup table
→ ledia:那對於特徵明顯的資料應該是可以壓到小很多的
→ ledia:要查時再 runtime 一個一個解出來
推 macbuntu:ksmrt0123 強者 XD