Big(O)可以通过测量得到肯定吗？

Question

假设您设计了一种算法,您可能认为该算法在O(n)中运行.如果我用1000输入测量运行的时间,然后将输入增加10倍,然后再次测量.如果运行时间几乎是第一次尝试的10倍,我可以推断O(n)是正确的吗？

这有多愚蠢？显然重复测试会提供更好的准确性,但我想知道这是否有意义.

Answer 1

通常,答案是'是'.如果将问题大小增加10并且时间增加10,那么假设O(N)可能是正确的.然而,这个数字不太可能如此美丽.

如果从1,000到10,000,O(N.logN)算法大致上升了13倍(见bc下文).那距离10不远,你可能会错误地认为增加12表示O(N.logN)而不是O(N).但是,如果你增加10并且时间增加大约100,你很可能会处理非线性算法 - O(N ²).所以,2分是不够的,但它是指示性的.多次运行和更多数据点都有帮助.

但有时候,还会有其他东西开始.例如,你可能会突然开始使用这么多内存,以至于你的程序被分页而不是只是运行.即使算法在给定足够资源的情况下仍然是线性的,它也会急剧减速.

此外,请注意缓存效果和优化效果.缓存可以使事情看起来更快.如果优化器断定计算被忽略,则可能会消除整个计算.所以你必须谨慎.

但是,运气好的话,你可以将问题扩展几个数量级(或者至少是几个不同的数字),然后对它是线性还是其他东西进行合理的猜测.

O(N.logN)为1,000对10,000

$ bc -l
n=1000
n*l(n)
6907.75527898213705205000
a=n*l(n)
m=n*10
m*l(m)
92103.40371976182736070000
b=m*l(m)
b/a
13.33333333333333333333
quit
$

Answer 2

与其他答案相反,我会说"不".但是,你可以得到一个很好的猜测(甚至不是估计,因为这里不合适).这可能是"经常"的意思.

问题是,你永远不知道常数因素.Big Oh是无症状的行为(在无限远中),除了最成长的术语之外,这是非常有用的.所以在数学上你不能确认你的假设.

首先,当无症状行为在现实应用中无用时,这里有大量算法和用例.仅仅因为"典型用例"输入分布下降.这种情况更常见.你仍然可以测试/"估计"它.

但也有一种情况,即最佳算法具有如此大的常数因子,因此不适用于现代系统.我所知道的最好的例子是大数乘法算法.

然而,存在一些系统"近似"(更好地说是猜测)算法的复杂性类别.我不确定codility是通过代码分析来测量它还是通过代码分析来猜测它们,但是他们能够做到这一点:https://codility.com/public-report-detail/ .

可以做的是运行算法,改变输入大小,运行测试并使数据适合模型.这很简单.然后你可以说,对于测试的输入范围,算法表现为 O(class(n)).(这可能具有实际意义,甚至比理论上的渐近复杂度更有价值.)

请注意,选择测试点并非易事.基本上,如果您的算法表现"快",那么您需要将输入大小率提高到下一个类.例如,如果你有类似的东西(100n+n!)可以去,n={1,10,100}因为它会kill执行时间.然而,去n={1,2,3,4,5,6,7}不会拿起n!部分(好吧7!,5040但是因为n^2它会更难).

最重要的是,得到一个好的猜测肯定是可能的,但除了大多数简单的情况,它可能是棘手的,很难做到,遗憾的是很难判断案件是否棘手.

此外,这个讨论纯粹是理论上的,省略了硬件效应.我听说算法的n^2表现比n^log n以前总是(非常)缓存友好,但不记得我的话,我不记得源.