Re: [問題] 陣列的替代品
※ 引述《snobbery (egoist)》之銘言：
: 如果我有一個n items的陣列A,
: 現在, 如果我想把儲存空間降到o(n),
你想用不到 n 的空間存 n 個資料。
所以顯然必須允許有的東西不見或是不準，
那我們就換個想法，其實你需要的是一個函數，map，或是什麼東西管他的，
讓你可以 A[i] -> v，但是你希望不要用到 O(n)，
那我們能不能只存一半？反正允許錯誤，
不行，O(n/2)還是 O(n)，不是 o(n)，
那存 1/3 呢？也不行。
存 logn 個？可以。
那存 0 個不是更好？
好，答案出來了 -"-
你就建寫一個函數，不管吃什麼都 return 0 就好了。
上面是開玩笑的，傳回 0 的話根本沒有用，
其實你需要的是一個函數，
一個「可以讓你對於 input 盡可能輸出正確 output 的函數，」
而且這個函數的 encoding 需要的資訊量要是 o(n)。
隨便給一個簡單的解法：
假設你有 n 個數字，
那你就弄個 logn 次的多項式 f(x) = a0 + a1 x + a2 x^2 + ..
但是你不知道參數是多少阿，要怎麼求得參數？
這個問題可以被轉化一個 machine learning 的問題，
你用 machine learning 去把參數學出來，
之後每次拿到 x，就帶入 f() 就可以了。
因為只有 logn 次，所以使用的記憶體是 O(logn)，滿足需求。
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.107.13
推
03/21 01:31, , 1F
03/21 01:31, 1F
→
03/21 01:33, , 2F
03/21 01:33, 2F
→
03/22 22:40, , 3F
03/22 22:40, 3F
→
03/22 22:40, , 4F
03/22 22:40, 4F
推
04/15 11:30, , 5F
04/15 11:30, 5F
推
04/15 11:36, , 6F
04/15 11:36, 6F
→
04/15 11:37, , 7F
04/15 11:37, 7F
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
