作者snobbery (egoist)
看板CSSE
标题[问题] 阵列的替代品
时间Tue Mar 17 17:10:20 2009
如果我有一个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
1F：推 TroyLee:log(q) 已经是常数不是吗? 03/17 19:59
2F：→ snobbery:但是log(q)*n仍然是O(n)啊~ 03/17 22:08
3F：推 Huangs:如果 q < n 那用 counting sort 的方式来存 03/17 22:21
4F：推 ksmrt0123:既然允许查询item有错误, 那都回0吧... constant time! 03/17 23:04
5F：→ ksmrt0123:且不需什麽 data structure 03/17 23:05
6F：推 ledia:压缩 / 解压缩呢 ? 如果允许存一个 fix size lookup table 03/18 12:01
7F：→ ledia:那对於特徵明显的资料应该是可以压到小很多的 03/18 12:02
8F：→ ledia:要查时再 runtime 一个一个解出来 03/18 12:02
9F：推 macbuntu:ksmrt0123 强者 XD 03/21 11:53