看板 [ CSSE ]
討論串[問題] 陣列的替代品
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 陣列的替代品
推噓5(5推 0噓 4→)留言9則，0人參與, 最新作者snobbery (egoist)時間15年前 (2009/03/17 17:10), 編輯資訊
2
0
0
內容預覽:
如果我有一個n items的陣列A,. 每個item都是0 ~ q之間的數值,. 那可以知道要存下這個陣列要花O(n)的儲存空間,. (嚴格來說, 是log(q)*n bits). 然後每次我要查詢第i個位置的item的話, 我需要花的時間是O(1),. (反正下個A[i]的指令就馬上取到i-th
(還有17個字)
#2
Re: [問題] 陣列的替代品
推噓3(3推 0噓 4→)留言7則，0人參與, 最新作者yoco315 (眠月)時間15年前 (2009/03/20 22:48), 編輯資訊
0
0
0
內容預覽:
你想用不到 n 的空間存 n 個資料。. 所以顯然必須允許有的東西不見或是不準，. 那我們就換個想法，其實你需要的是一個函數，map，或是什麼東西管他的，. 讓你可以 A[i] -> v，但是你希望不要用到 O(n)，. 那我們能不能只存一半？反正允許錯誤，. 不行，O(n/2)還是 O(n)，不是
(還有415個字)
#3
Re: [問題] 陣列的替代品
推噓3(3推 0噓 8→)留言11則，0人參與, 最新作者semop (semop)時間15年前 (2009/03/21 16:48), 編輯資訊
0
0
0
內容預覽:
那就做一個較小的有 m 個資料的陣列 B. 按照某種排序方式（相同資料的出現數目或查詢次數等等）. 將 A 的資料的依序填入. 並建立陣列 C 使得 C[n] < m 時, B[C[n]] == A[n]. 於是只要足夠小的 m 值，就能減少資料所需空間. 簡單來說，這樣的資料結構當然存在，它的名字
首頁
上一頁
1
下一頁
尾頁