Big(O) 可以通过测量来确认吗？
Can Big(O) be affirmed by measurement?
假设您设计了一种算法，您可能认为 O(n) 为 运行s。如果我用 1000 个输入测量时间 运行s，然后将输入增加 10 倍，然后再次测量。我可以推断 O(n) 是正确的当且仅当 运行 时间几乎是第一次尝试的 10 倍吗？
这有多愚蠢？显然重复测试会提供更好的准确性，但我想知道这是否有意义。
通常，答案是 'yes'。如果您将问题大小增加 10 并且时间增加 10，则假设 O(N) 可能是正确的。不过，这个数字不太可能这么漂亮。
如果您从 1,000 增加到 10,000，O(N.logN) 算法将大致增加 13 倍（参见下面的 bc）。这与 10 相差不远，您可能会错误地认为增加 12 表示 O(N.logN) 而不是 O(N)。但是，如果您增加 10 并且时间增加了大约 100，您可能正在处理非线性算法 — 可能是 O(N2)。所以，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
$
与其他答案相反，我会说“不”。但是，您可以得到一个很好的猜测（甚至不是估计，因为它在这里不合适）。这大概就是“经常”的意思吧。
问题是，你永远不知道常数因子。 Big Oh 是渐近行为（在无穷大），这对于删除除增长最快的项以外的所有内容非常有用。所以在数学上你无法证实你的假设。
首先，当渐近行为在现实生活中的应用程序中没有用时，这里有很多算法和用例。仅仅是因为“典型用例”输入分布下降。这种情况比较常见。你仍然可以测试/“估计”它。
但也有一种情况，即最好的算法具有如此大的常数因子，以至于不适用于现代系统。我知道的最好的例子是 large number multiplication algorithms.
但是，有些系统“近似”（更好的说法是猜测）算法的复杂性 class。我不确定 Codility_ 是测量它还是通过代码分析得到他们的猜测，但他们能够做到：https://app.codility.com/public-report-detail/.
可以做的是 运行 一种算法，并更改输入大小，运行 测试并将数据拟合到模型中。这很简单。那么你可以说对于测试的输入范围，算法 的行为与 O(class(n)) 相同。 （这可能具有比理论上的渐近复杂性更有价值的实际意义。）
请注意，选择测试点并非易事。基本上，如果您的算法表现得“快”，那么您需要将输入大小速率提高到下一个 class。例如。如果你有类似 (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 表现更好的算法，因为前者总是（非常）缓存友好，但不要相信我的话，我不记得来源。
根据实际程序的 运行 时间绘制输入大小是一个非常有用的工具，可以让您了解代码的实际执行情况。一般来说，认为可以使用它来推断复杂性是很危险的。
这是它分解的一种方式的实际例子。
好的快速排序实现将数组分为三个部分：小于主元、等于主元和大于主元。这意味着快速排序随机数组 64 位整数（实际上，排序任何固定大小数据类型的随机数组）使用 O(n) 比较，因为最终每个子数组都是常量。
不幸的是，您无法根据经验看到这一点：如果您根据比较次数绘制 n，则该图看起来像 n*log(n)，直到输入数组变得比 2^64 个元素大得多。即使您有足够的内存，您的编程语言也可能不允许您索引该大小的数组。
这个例子也证明了经验测量给了你有趣的数据（代码在实际输入上的表现类似于 n*log(n)），复杂性给了你一个理论上但实际上无用的事实，即渐近增长是线性的。
除了别人说的。有时平均情况和最坏情况可能不同，最坏情况可能很难找到。一个著名的例子是 quicksort，其 O(n log n) 平均行为（滥用 O 符号？），以及 O(n^2) 最坏情况行为。如果你得到了一个 "black-box" 算法（好吧，程序），那么在不了解该算法的情况下，这种最坏的情况可能很难通过实验捕捉到。
假设您设计了一种算法，您可能认为 O(n) 为 运行s。如果我用 1000 个输入测量时间 运行s，然后将输入增加 10 倍，然后再次测量。我可以推断 O(n) 是正确的当且仅当 运行 时间几乎是第一次尝试的 10 倍吗？
这有多愚蠢？显然重复测试会提供更好的准确性，但我想知道这是否有意义。
通常，答案是 'yes'。如果您将问题大小增加 10 并且时间增加 10，则假设 O(N) 可能是正确的。不过，这个数字不太可能这么漂亮。
如果您从 1,000 增加到 10,000，O(N.logN) 算法将大致增加 13 倍（参见下面的 bc）。这与 10 相差不远，您可能会错误地认为增加 12 表示 O(N.logN) 而不是 O(N)。但是，如果您增加 10 并且时间增加了大约 100，您可能正在处理非线性算法 — 可能是 O(N2)。所以，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
$
与其他答案相反，我会说“不”。但是，您可以得到一个很好的猜测（甚至不是估计，因为它在这里不合适）。这大概就是“经常”的意思吧。
问题是，你永远不知道常数因子。 Big Oh 是渐近行为（在无穷大），这对于删除除增长最快的项以外的所有内容非常有用。所以在数学上你无法证实你的假设。
首先，当渐近行为在现实生活中的应用程序中没有用时，这里有很多算法和用例。仅仅是因为“典型用例”输入分布下降。这种情况比较常见。你仍然可以测试/“估计”它。
但也有一种情况，即最好的算法具有如此大的常数因子，以至于不适用于现代系统。我知道的最好的例子是 large number multiplication algorithms.
但是，有些系统“近似”（更好的说法是猜测）算法的复杂性 class。我不确定 Codility_ 是测量它还是通过代码分析得到他们的猜测，但他们能够做到：https://app.codility.com/public-report-detail/.
可以做的是 运行 一种算法，并更改输入大小，运行 测试并将数据拟合到模型中。这很简单。那么你可以说对于测试的输入范围，算法 的行为与 O(class(n)) 相同。 （这可能具有比理论上的渐近复杂性更有价值的实际意义。）
请注意，选择测试点并非易事。基本上，如果您的算法表现得“快”，那么您需要将输入大小速率提高到下一个 class。例如。如果你有类似 (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 表现更好的算法，因为前者总是（非常）缓存友好，但不要相信我的话，我不记得来源。
根据实际程序的 运行 时间绘制输入大小是一个非常有用的工具，可以让您了解代码的实际执行情况。一般来说，认为可以使用它来推断复杂性是很危险的。
这是它分解的一种方式的实际例子。
好的快速排序实现将数组分为三个部分：小于主元、等于主元和大于主元。这意味着快速排序随机数组 64 位整数（实际上，排序任何固定大小数据类型的随机数组）使用 O(n) 比较，因为最终每个子数组都是常量。
不幸的是，您无法根据经验看到这一点：如果您根据比较次数绘制 n，则该图看起来像 n*log(n)，直到输入数组变得比 2^64 个元素大得多。即使您有足够的内存，您的编程语言也可能不允许您索引该大小的数组。
这个例子也证明了经验测量给了你有趣的数据（代码在实际输入上的表现类似于 n*log(n)），复杂性给了你一个理论上但实际上无用的事实，即渐近增长是线性的。
除了别人说的。有时平均情况和最坏情况可能不同，最坏情况可能很难找到。一个著名的例子是 quicksort，其 O(n log n) 平均行为（滥用 O 符号？），以及 O(n^2) 最坏情况行为。如果你得到了一个 "black-box" 算法（好吧，程序），那么在不了解该算法的情况下，这种最坏的情况可能很难通过实验捕捉到。