0

有没有办法生成一个函数 F，给定一个序列，例如：

seq = [1 2 4 3 0 5 4 2 6]

那么 F(seq) 会返回一个生成该序列的函数吗？那是，

F(seq)(0) = 1
F(seq)(1) = 2
F(seq)(2) = 4
... and so on

另外，如果是，那么最低复杂度的函数是什么，生成的函数的复杂度是多少？

编辑 似乎我不清楚，所以我将尝试举例说明：

F(seq([1 3 5 7 9])} 
# returns something like:
F(x) = 1 + 2*x
# limited to the domain x ∈ [1 2 3 4 5]

换句话说，我想计算一个可用于代数的函数，使用 +、* 等数学函数恢复整数序列，即使你从内存中清除了它。我不知道这是否可能，但是，因为人们可以很容易地为琐碎的情况编写这种函数的近似值，所以我想知道它走了多远，以及是否有一些关于它的实际研究。

编辑 2回答另一个问题，我只对整数序列感兴趣——如果这很重要的话。

如果还不清楚，请告诉我！

4

3 回答 3

3

好吧，如果你只是想知道一个带有“+和*”的函数，也就是说，一个多项式，你可以去维基百科查看拉格朗日多项式（https://en.wikipedia.org/wiki/Lagrange_polynomial）。它为您提供编码序列的最低次数多项式。

不幸的是，您可能无法存储比以前更少的内容，因为多项式的度数为 d=n-1 的概率，其中 n 是数组的大小，对于随机整数来说非常高。此外，您将不得不存储有理数而不是整数。最后，与数组的 O(1) 相比，对任意数量的数组的访问将在 O(d) 中（使用霍纳算法进行多项式评估）。

不过，如果您知道您的序列可能非常简单且非常长，那么它可能是一种选择。

于 2013-09-28T09:58:51.820 回答
3

如果序列来自一个低次数的多项式，那么找到生成它的唯一多项式的一种简单方法是使用牛顿级数。构造一个数字的多项式具有 O(n²) 的时间复杂度，并且评估它具有 O(n)。

在牛顿级数中，多项式用 x、x(x-1)、x(x-1)(x-2) 等表示，而不是更熟悉的 x、x²、x³。为了得到系数，基本上你计算序列中后续项目之间的差异，然后计算差异之间的差异，直到只剩下一个或者你得到一个全零的序列。你在底部得到的数字，除以项的阶乘，就可以得到系数。例如，对于第一个序列，您会得到以下差异：

1  2  4  3  0  5   4   2    6
   1  2 -1 -3  5  -1  -2    4 
      1 -3 -2  8  -6  -1    6
        -4  1 10 -14   5    7
            5  9 -24  19    2
               4 -33  43  -17
                 -37  76  -60
                     113 -136
                         -249

因此，生成这个序列的多项式是：

f(x) = 1 + x(1 + (x-1)(1/2 + (x-2)(-4/6 + (x-3)(5/24 + (x-4)(4/120 
         + (x-5)(-37/720 + (x-6)(113/5040 + (x-7)(-249/40320))))))))

这与您使用其他技术（如拉格朗日插值法）得到的多项式相同；这只是生成它的最简单方法，因为您可以获得可以使用霍纳方法评估的多项式形式的系数，这与拉格朗日形式不同。

于 2013-09-28T10:44:44.673 回答
2

如果你说这个序列可以是完全随机的，那没有什么神奇的。然而，它总是可能的，但不会节省你的记忆。在最坏的情况下，任何插值方法都需要相同数量的内存。因为，如果不这样做，就有可能将所有内容压缩到一个位。

另一方面，有时可以使用蛮力、一些启发式方法（如遗传算法）或数值方法来重现某种具有指定类型的数学表达式，但祝你好运:)

只需使用一些归档工具来节省内存使用。

我认为阅读此内容对您很有用：http://en.wikipedia.org/wiki/Entropy_(information_theory)

于 2013-09-28T09:10:32.150 回答