Re: [問題] 陣列的替代品

[yoco315 (眠月)]

※ 引述《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
推 Huangs:第一段不對  用 O(q) 的空間就足以精確地存下 n 個數字
→ Huangs:當 q < n 時   所需的空間就少於 O(n) 了
→ yoco315:我有問題 ^^/  我看不懂  orz
→ yoco315:大大講更清楚一點 orz 拜託
推 HudsonE:q < n 是指...??? 只要 q = kn, const k!= 0 那就是 O(n)
推 HudsonE:如果 q 是原文的 q... 那根本存不下 n 的序列
→ HudsonE:另, 本文是正解 XD