从运行时间确定时间复杂度的最简单方法

Question

假设我正在尝试分析一个算法，而我所能做的就是使用不同的输入来运行它。我可以构造一组点 (x,y) 作为（样本大小，运行时间）。 我想动态地将算法分类为复杂性类别（线性、二次、指数、对数等） 理想情况下，我可以给出一个或多或少近似该行为的方程。 我只是不确定最好的方法是什么。

对于任何次数多项式，我都可以创建回归曲线并提出一些适合度的度量，但我真的不知道如何对任何非多项式函数执行此操作。这比较困难，因为我之前不知道我应该尝试适应什么形状。

这可能更像是一个数学问题而不是编程问题，但这对我来说非常有趣。我不是数学家，所以可能有一种更简单的既定方法可以从一组我不知道的点中获得合理的函数。有没有人有解决这样的问题的想法？是否有 C# 数字库可以帮助我处理数字？

Answer 1

好吧，您真正关心的复杂性类别并不多，所以我们可以说：线性、二次、多项式（次数 > 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

现在可以比较每个函数与剩余数据的拟合程度，这是一个图：

我们 我无法发布图像，因此请查看此处的情节：https://i.sstatic.net/UH6T8。 png

真实数据用红色星号显示，线性用绿线显示，二次用蓝色显示，多项式用黑色显示，指数用粉色显示，对数图用绿色显示，带 O。从残差中应该可以清楚地看出什么函数最适合您的数据。

Answer 2

曲线拟合曾经是一门艺术，但现在在某种程度上已经颓废了:)（这对周围的物理学家来说是一个笑话）

已经取得了很多进展，这使得简单的凡人能够猜测（一些）不平凡的函数依赖关系。

我不会详细介绍这些方法和限制，而是建议您参考 eureqa，这是康奈尔大学开发的一个非常好的软件。

Eureqa（发音为“eureka”）是一款用于检测数据中的方程和隐藏数学关系的软件工具。其目标是确定可以描述生成数据的基本机制的最简单的数学公式。 Eureqa 可免费下载和使用。查找程序下载、视频教程、用户论坛以及其他参考资料。

我尝试了好几次eureqa，如果模型不是太复杂的话，效果非常好。我认为它足以区分多项式、对数和指数。

哈！

后记：

遗憾的是该软件不再免费了:(