[問題] 陣列的替代品

看板CSSE作者snobbery (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

推

TroyLee

03/17 19:59, , 1^F

03/17 19:59, 1^F

→

snobbery

03/17 22:08, , 2^F

03/17 22:08, 2^F

推

Huangs

03/17 22:21, , 3^F

03/17 22:21, 3^F