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

Question

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

我想要的是估计给定输出和输入的数学函数。是更接近f(N)、f(N^2)、log(N)、N*lolg(N)还是2^N.

的形式

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

Answer 1

您可以使用 Least Squares 方法找到与您的数据距离最小的函数。

假设您有一个未知函数的样本观察列表，其形状为一些阶数对 (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))

输出

这意味着第 4 个函数最接近我们的示例数据 n*log(n)。

请注意，如果我们像这样减少样本数据的大小（去掉一半的样本数据）：

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

这个程序将打印1，这意味着最接近的函数是n²。由此可见样本数据的重要性。

Answer 2

这是对 sudomakeinstall2 的回答的一个小补充。

在大 O 表示法中，您不关心常量缩放。因此，您实际上想要测量 ( y - k * g(x) )^2，而不是像他的回答那样测量距离 ( y - 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)
...

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

How to estimate mathematical function by input and output values?

c#

algorithm

math

curve-fitting