algorithm - 如何生成一个将对序列进行代数编码的函数？

Question

有没有办法生成一个函数 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]

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

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

如果还是不清楚，请告诉我!

Answer 1

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

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

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