假设我正在尝试分析一种算法，而我所能做的就是使用不同的输入运行它。我可以构建一组点 (x,y) 作为（样本大小，运行时间）。我想将算法动态分类为复杂性类（线性、二次、指数、对数等）。理想情况下，我可以给出一个或多或少近似于行为的方程。我只是不确定最好的方法是什么。
对于任何次数多项式，我可以创建回归曲线并提出一些适应度测量，但我真的不知道如何为任何非多项式函数做到这一点。这更难，因为我以前不知道我应该尝试适合什么形状。
这可能更像是一个数学问题而不是编程问题，但这对我来说非常有趣。我不是数学家，所以可能有一种更简单的既定方法可以从一组我不知道的点中得到一个合理的函数。有没有人有任何想法来解决这样的问题？是否有 C# 的数字库可以帮助我处理数字？
好吧，您真正关心的复杂性类别并不多，因此假设：线性、二次、多项式（次数 > 2）、指数和对数。
对于其中的每一个，您都可以使用最大的 (x,y) 对来求解未知变量。让 y = f(x) 将算法的运行时间表示为样本量的函数。假设 f(1) = 0，如果不是，我们总是可以从每个 y 中减去该值 y(1)，这只是消除了 f(x) 中的常数。让 y(end) 表示 (x,y) 数据集中 y 的最后一个（也是最大值）值。
在这一点上，我们可以解决每个规范形式的未知数：
f(x) = c*x
f(x) = c*x^2
f(x) = x^c
f(x) = c^x
f(x) = log(x)/log(c)
由于每个方程中只有一个未知数，我们可以任意点求解它。考虑从随机次数 > 2 的多项式生成的以下数据：
x = [ 1 2 3 4 5 6 7 8 9 10 ];
y = [ 0 6 19 44 81 135 206 297 411 550 ];
如果我们使用最后一点来求解每种可能性的 c（假设这将是最小的噪声估计）
550 = c*10 -> c = 55
550 = c*10^2 -> c = 5.5
550 = 10^c -> c = log(550)/log(10) ~= 2.74
550 = c^10 -> c = 550^(1/10) ~= 1.88
550 = log(x)/log(c) -> c = 10^(1/550) ~= 1.0042
我们现在可以比较这些函数中的每一个对剩余数据的拟合程度，这是一个图：
I'm new and I can't post images so look at the plot here: http://i.stack.imgur.com/UH6T8.png
The true data is shown in the red asterisk, linear with green line, quadratic in blue, polynomial in black, exponential in pink, and the log plot in green with O's. It should be pretty clear from the residuals what function fits your data the best.
曲线拟合曾经是一门艺术，但现在不知何故腐朽了:)（这对周围的物理学家来说是个笑话）
已经取得了很多进展，这允许简单的凡人猜测（一些）非平凡的函数依赖关系。
我不会详细介绍方法和限制，而是建议您参考eureqa，这是康奈尔大学开发的一款非常棒的软件。
Eureqa（发音为“eureka”）是一种软件工具，用于检测数据中的方程和隐藏的数学关系。它的目标是确定最简单的数学公式，这些公式可以描述产生数据的基本机制。Eureqa 可以免费下载和使用。寻找程序下载、视频教程、用户论坛和其他参考资料。
如果模型不太复杂，我尝试了 eureqa 几次，结果非常好。我认为它足以区分多项式、对数和指数。
！
遗憾的是，该软件不再免费了:(
