PTT數位生活區 / CSSE (電腦科學及軟體工程)

[問題] 陣列的替代品

看板CSSE (電腦科學及軟體工程)作者 (egoist)時間15年前 (2009/03/17 17:10), 編輯推噓5(5推 0噓 4→)
留言9則, 6人參與, 最新討論串1/3 (看更多)
如果我有一個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/17 19:59, , 1F
log(q) 已經是常數不是嗎?
03/17 19:59, 1F
→
03/17 22:08, , 2F
但是log(q)*n仍然是O(n)啊~
03/17 22:08, 2F
推
03/17 22:21, , 3F
如果 q < n 那用 counting sort 的方式來存
03/17 22:21, 3F
推
03/17 23:04, , 4F
既然允許查詢item有錯誤, 那都回0吧... constant time!
03/17 23:04, 4F
→
03/17 23:05, , 5F
且不需什麼 data structure
03/17 23:05, 5F
推
03/18 12:01, , 6F
壓縮 / 解壓縮呢 ? 如果允許存一個 fix size lookup table
03/18 12:01, 6F
→
03/18 12:02, , 7F
那對於特徵明顯的資料應該是可以壓到小很多的
03/18 12:02, 7F
→
03/18 12:02, , 8F
要查時再 runtime 一個一個解出來
03/18 12:02, 8F
推
03/21 11:53, , 9F
ksmrt0123 強者 XD
03/21 11:53, 9F
‣ 更多 snobbery 的文章
文章代碼(AID): #19lsZz1D (CSSE)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
CSSE 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 snobbery 的文章
文章代碼(AID): #19lsZz1D (CSSE)