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