如何通过输入和输出值来估计数学函数

Question

对于这些输入值，我有一些N imputes和相应的函数输出。

我想要估计给定输出和输入的数学函数。是否更接近于f(N)、f(N^2)、log(N)、N*lolg(N)或2^N的形式?

本质上，我想做的是估计大o。因此，n是输入数据量，输出是计算时间。所以基本上我想至少知道我的函数与上面提到的哪个函数更接近。

Answer 1

您可以使用最小二乘法找到与数据距离最小的函数。

假设您有一个未知函数的样本观察列表，其形状为某些阶对(x,y)或(x,f(x))。你可以用最小二乘法测量这个未知函数到某个已知函数g的距离。

distance = 0
for x,y in sample pairs
    distance += ( y - g(x) )^2

这个距离越小未知函数就越接近已知函数g

现在，如果你想找到最接近你未知函数的函数(从一个预先确定的函数列表中)，你只需要计算每个函数到你未知函数的距离。距离最小的函数与未知函数更接近。

请注意，此方法是近似值，并不是100%准确，但您可以通过提供更大和更全面的样本数据来提高其准确性

---

下面是一个示例Python实现:

import math
functions = []
functions.append( lambda n: n )                # y = n
functions.append( lambda n: n*n )              # y = n^2
functions.append( lambda n: math.log(n,2) )    # y = log(n)
functions.append( lambda n: n*math.log(n,2) )  # y = n*log(n)
functions.append( lambda n: 2**n )             # y = 2^n
# creating the sample data the unknown function is n + 10*n*log(n)
pairs = [ (n, n + 10*n*math.log(n,2) ) for n in range(1,200,1) ]
# calculating the distance of each function to the sample data
# and add them to a list
distances = [ ]
for func in functions:
    d = 0
    for n,y in pairs:
        d += (func(n) - y)**2 
    distances.append(d)
# finding the minimum value and printing the index   
print distances.index(min(distances))

输出

3

这意味着第四个函数最接近我们的样本数据，即n*log(n)。

请注意，如果我们像这样减少样本数据的大小(去掉一半的样本数据):

pairs = [ (n, n + 10*n*math.log(n,2) ) for n in range(1,100,1) ]

这个程序将打印1，这意味着最接近的函数是n²。这显示了示例数据的重要性。

Answer 2

这是sudomakeinstall2回答的一个小附录。

在大0符号中，你不关心常数的缩放。因此，不像他回答的那样测量距离( y - g(x) )^2，您实际上想测量( y - k * g(x) )^2，其中k是最适合的常数缩放。这个k可以直接计算为最小二乘拟合。下面是修改后的版本，它应该更健壮:

...
for func in functions:
    #calculate the best k
    numerator = 0
    denominator = 0
    for n,y in pairs:
        numerator += func(n) * y
        denominator += func(n) * func(n)
    k = numerator / denominator
    d = 0
    for n,y in pairs:
        d += (k * func(n) - y)**2 
    distances.append(d)
...