5

如果 Big-O 符号不能提供所需的所有信息，那么它在计算机科学中的用途是什么？

例如，如果一种算法在 处运行，1000n而在 处运行n，则它们都是在处运行O(n)。但我仍然可能根据这些信息做出愚蠢的选择，因为对于任何给定的输入，一种算法所花费的时间是另一种算法的 1000 倍。

我仍然需要知道方程的所有部分，包括常数，才能做出明智的选择，那么这种“中间”比较的重要性是什么？当它被简化为这种形式时，我最终会丢失重要信息，我会得到什么？

4

7 回答 7

3

这个常数因子代表什么？例如，您不能肯定地说 O(1000n) 的算法会比 O(5n) 的算法慢。可能是 1000n 算法将所有数据加载到内存中并对该数据进行 1,000 次传递，而 5n 算法对存储在慢速 I/O 设备上的文件进行 5 次传递。1000n 算法将运行得更快，即使它的“常数”更大。

此外，某些计算机执行某些操作的速度比其他计算机更快。这是很常见的，给定两个 O(n) 算法（称为 A 和 B），A 在一台计算机上执行得更快，B 在另一台计算机上执行得更快。或者同一算法的两种不同实现在同一台计算机上可能具有广泛不同的运行时间。

正如其他人所说，渐近分析可以指示算法的运行时间如何随输入的大小而变化。它有助于为您提供算法选择的良好起点。快速参考会告诉您特定算法是 O(n) 或 O(n log n) 或其他什么，但很容易找到有关大多数常见算法的更详细信息。尽管如此，更详细的分析只会给您一个常数，而不会说明该数字与实际运行时间的关系。

最后，您可以确定哪种算法适合您的唯一方法是自己研究它，然后根据您的预期数据对其进行测试。

简而言之，我认为您对渐近分析的期望过高。这是一个有用的“第一行”过滤器。但是，当您超出此范围时，您必须寻找更多信息。

于 2013-10-23T15:03:47.630 回答
3

正如您正确指出的那样，它不会为您提供有关算法确切运行时间的信息。它主要用于指示算法的复杂性，指示它在输入大小、二次、指数等方面是否是线性的。如果您知道输入大小很大，这在选择算法时很重要，因为即使是1000n算法很好地击败了1.23 exp(n)足够大的算法n。

在现实世界的算法中，隐藏的“比例因子”当然很重要。因此，如果算法具有较低的比例因子，则使用复杂度“更差”的算法并不少见。排序算法的许多实际实现是例如“混合”，并且会求助于一些“糟糕”的算法，例如插入排序（O(n^2)实现起来非常简单）n < 10，同时更改为快速排序（O(n log(n))但更复杂）n >= 10。

于 2013-10-22T19:27:16.160 回答
2

它的主要目的是对逻辑进行粗略的比较。对于(n 大致等于 1000) 和，O(n)和的差异O(1000n)很大，但是当您将其与(n 远大于 1000) 的值进行比较时，差异很小。n ~ 1000n < 1000n >> 1000

您说得对，它们都是线性缩放的，知道系数有助于详细分析，但通常在计算线性 ( O(cn)) 和指数 ( O(cn^x)) 性能之间的差异时，比两个线性时间之间的差异更需要注意。在比较高阶的运行时（例如 和 性能差异呈指数级扩展）时存在较大的值。

Big O 表示法的总体目的是给出相对性能时间的感觉，以便比较和进一步优化算法。

于 2013-10-22T19:26:51.650 回答
2

除了常数项的隐藏影响外，复杂性表示法还只考虑问题的最坏情况。

例如，单纯形法（线性规划）对于所有已知的实现都具有指数复杂性。然而，单纯形法在实践中比可证明的多项式时间内点法工作得快得多。

复杂性符号对于理论问题分类具有很大价值。如果您想了解更多有关实际后果的信息，请查看 Spielman 的“平滑分析”： http ://www.cs.yale.edu/homes/spielman

这就是你要找的。

于 2013-10-22T19:58:13.993 回答
2

Big-O 告诉您进程的运行时或内存消耗如何随着其输入大小的变化而变化。O(n) 和 O(1000n) 仍然是 O(n) - 如果你将输入的大小加倍，那么出于所有实际目的，运行时间也会加倍。

现在，我们可以有一个 O(n) 算法和一个 O(n 2 ) 算法，其中 n 的系数为 1000000，n 2的系数为 1，在这种情况下 O(n 2 ) 算法将优于 O( n) 对于较小的 n 值。然而，这并没有改变第二个算法的运行时间比第一个算法增长得更快的事实，这就是 big-O 告诉我们的信息。O(n) 算法开始优于 O(n 2 ) 算法时，会有一些输入大小。

于 2013-10-22T19:28:21.103 回答
1

你是对的，它没有给你所有的信息，但是在任何领域都没有一个单一的指标可以做到这一点。

Big-O 表示法告诉您随着数据集变大，性能会以多快的速度变差。换句话说，它描述的是性能曲线的类型，而不是绝对的性能。

于 2013-10-22T19:27:08.810 回答
0

一般来说，Big-O 符号对于表示算法的缩放性能很有用，因为它属于三个基本类别之一：

  • 线性
  • 对数（或“线性”）
  • 指数的

可以对算法进行深入分析以进行非常准确的性能测量，但这很耗时，而且并不是真正需要获得广泛的性能指标。

于 2013-10-22T19:29:54.307 回答