代码之家 › 专栏 › 技术社区 › captncraig

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

curve-fitting big-o complexity-theory math

1

captncraig · 技术社区 · 15 年前

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

对于任何程度的多项式,我都可以创建回归曲线,并提出一些适合性的度量,但我真的不知道如何对任何非多项式函数这样做。更难的是,我以前不知道我应该试着去适应什么样的体型。

这可能更像是一个数学问题,而不是编程问题,但对我来说很有趣。我不是数学家,所以可能有一个更简单的方法,从我不知道的一组点中得到一个合理的函数。有人对解决这样的问题有什么想法吗?有没有C的数字库可以帮助我计算数字?

2 回复 | 直到 11 年前

1

2

fairidox 15 年前

好吧,没有那么多你真正关心的复杂度类,所以让我们说:线性、二次、多项式(度gt;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

现在我们可以比较这些函数中的每一个与剩余数据的匹配程度,下面是一个图:

我是新来的,无法发布图片,请看下面的图: http://i.stack.imgur.com/UH6T8.png

真实数据显示在红色星号中,与绿线呈线性,蓝色为二次曲线,黑色为多项式,粉红色为指数,与O's呈绿色的对数图中。从残差中应该很清楚什么函数最适合您的数据。

2

1

Dr. belisarius 11 年前

曲线拟合曾经是一门艺术,但现在不知何故已经腐朽了:)(这对周围的物理学家来说是个笑话)

已经取得了很多进展,这使得简单的凡人可以猜测(一些)非平凡的功能依赖性。

我不会对方法和限制进行描述,但我会向您介绍 eureqa 这是康奈尔大学开发的一个非常好的软件。

eureqa(发音为“eureka”)是一个软件工具,用于检测方程和数据中隐藏的数学关系。它的目标是找出最简单的数学公式,可以描述产生数据的基本机制。Eureqa可免费下载和使用。查找程序下载、视频教程、用户论坛等参考资料。

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

嗯!

后稿:

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