※ 引述《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