Jef*_*eff 5 algorithm computer-science
如果不提供所需的所有信息,Big-O符号在计算机科学中的用途是什么？
例如,如果一个算法在一个算法1000n和一个算法运行n,那么它们都是O(n).但是我仍然可以根据这些信息做出愚蠢的选择,因为对于任何给定的输入,一种算法需要1000倍的长度.
我仍然需要知道等式的所有部分,包括常数,以做出明智的选择,那么这种"中间"比较的重要性是什么？当它被缩减到这种形式时,我最终会丢失重要信息,我会获得什么？
这个常数因子代表什么？例如，您不能肯定地说 O(1000n) 的算法会比 O(5n) 的算法慢。1000n 算法可能会将所有数据加载到内存中，并对这些数据进行 1,000 次传递，而 5n 算法可能会对存储在慢速 I/O 设备上的文件进行 5 次传递。1000n 算法将运行得更快，尽管它的“常数”要大得多。
此外，某些计算机执行某些操作的速度比其他计算机快。这是很常见的，给定两个 O(n) 算法（称为 A 和 B），A 在一台计算机上执行得更快，B 在另一台计算机上执行得更快。或者，同一算法的两种不同实现在同一台计算机上的运行时间可能相差很大。
正如其他人所说，渐近分析可以让您了解算法的运行时间如何随输入的大小而变化。它对于为您选择算法提供一个良好的起点很有用。快速参考会告诉您特定的算法是 O(n) 或 O(n log n) 或其他什么，但很容易找到有关最常见算法的更多详细信息。尽管如此，更详细的分析只会给您一个常数，而不会说明该数字与实际运行时间的关系。
最后，确定哪种算法适合您的唯一方法是自己研究它，然后根据您的预期数据对其进行测试。
简而言之，我认为您对渐近分析的期望过高。这是一个有用的“一线”过滤器。但当你超越这个范围时，你必须寻找更多信息。