可能的重复：
复杂性。为什么常数不重要？
我有一个关于代码/算法复杂性的简单问题。我非常了解基本的复杂性概念，例如相对于输入的增长顺序，为什么 O(n) 优于 O(n^2) 等。但是，我不确定常量是否真的重要，因为它似乎对我来说，他们应该但没有人考虑或谈论他们。您能否改进具有相同复杂性的代码。可以说我有一个具有一定顺序复杂性的代码可以说 O(n)。假设此代码在 10 分钟内运行某些输入。如果我重复两次代码，现在代码在 20 分钟内运行会怎样。尽管复杂性相同，但 20 分钟超过 10 分钟是一件大事。无论复杂性如何，这些事情是否重要？如果不是为什么？如果是，为什么？请解释。
在理论复杂性分析中，系数根本不重要。在实践中，它们非常重要。这就是为什么几乎每个人仍然使用（指数复杂度）单纯形算法而不是（多项式复杂度）内点算法来解决优化问题。
如果您正在进行算法分析并想知道 O() 行为，那么常量是无关紧要的。如果您想知道对于特定范围的问题，哪段代码运行得更快，那么一切都很重要。
我认为您将复杂性的真实概念与不同的性能示例混合在一起。通过复杂性，我们的意思是：如果 n 增长，处理步骤增长的顺序是什么。
例如，您正在执行线性搜索，在这种情况下您的订单是 O(n)。这里的意思是：如果 n = 5，并且需要 5 秒，那么对于 n=10，将需要 10 秒，即关系是线性的。
没有区别，如果顺序是 O(5n)，即相同的搜索需要 25 秒，n=5，然后对于 n=10，需要 50 秒。我仍然可以说，它的 O(n) 即直接依赖。
同样的例子也适用于 O(n^2) 的排序算法。
在您的示例中，提到的改进确实很重要，但它不会改变复杂性的顺序，即关系。如果我们可以将处理时间减少两倍，这是一个很大的改进，前提n是数量很大，例如时间从 20 分钟减少到 10 分钟。如果您更改算法以改变所用时间与 n 增长的关系，那么 O(n) 也会改变:)
这是理论和实践之间的很大差异。为此有几点需要考虑：
对于实际实现，这些常量可能不清楚。您通常无法从给定的实现中确定这些常量。举个例子，你有两个 O(N) 算法来解决同一个问题，但是一个需要 2N 次操作，第二个只需要 N 次操作。人们可能会认为具有 N 次操作的那个运行得更快，但事实可能并非如此。由于更好的缓存或管道使用等，我们可能有 2N 个操作，每个操作只需要 1 个周期，而另一种算法可能需要 N 个操作，每个操作需要 4 个周期。所以运算多的算法可能还是会更快。在不同的硬件上，这可能看起来非常不同。因此，除非您知道确切的硬件，否则理论分析是一个很好的指南。在真正的硬件上，交互通常非常复杂，只有基准测试才能给你一个很好的提示。
对于实时系统，情况又大不相同。在这里，人们通常对最坏情况执行时间 (WCET) 感兴趣，它指的是算法可能花费的实际时间。在这种情况下，常量确实很重要。然而，在这种情况下，问题的大小也是已知的（通常是来自几个传感器的一组输入），因此分析有很大不同。
硬件的影响可能会变得如此之大，以至于理论上看起来更糟糕的算法实际上可能优于看起来更好的算法，至少对于所有相关的问题大小。使用树的算法（通常在理论上更好）与使用平面数组结构的算法（通常在理论上更差）的情况通常是这种情况。然而，通常平面数组更好，因为它可以更有效地缓存。但是，有时可以使用两全其美的方法，例如在将堆实现为数组时（这几乎总是优于排序树）。
复杂性理论并不重要，它只对函数如何随着输入大小的增长而缩放感兴趣。
常数根本不会影响函数在输入大小向无穷大增长时的行为方式。
但是，如果您对实际运行某段代码感兴趣，您可能会对较大的常量开销以及函数如何在较小的输入大小下执行感兴趣。
复杂性理论与实践的区别。
这是这个问题的一个很好的答案。
当然，如果你的算法比它需要的慢两倍，这很重要。关键是，我们关心算法在“n”方面的性能，因为“n”有可能非常大。
让我们举一个实际的例子。假设您有一个包含 n 个项目的列表。您的算法遍历列表一次。那是订单n。如果它遍历列表两次，那可能会花费更长的时间，而且速度会更慢——如果没有必要，你不应该这样做。
但是从长远来看，n^2 算法的影响比 2*n 算法大得多。随着 n 越来越大，n^2 和 2*n 之间的差异也越来越大。
因此，要回答您的问题，是的，当程序运行速度减慢两倍时，这很重要。但是，如果它以指数速度变慢，那就更重要了。这就是我们关心 Big-Oh 的原因。但是对速度的任何改进显然对您的程序都有好处。
当随着 n 的增长将 O(n) 与 O(n^2) 进行比较时，常数将开始变得无关紧要。即使常数很大，这也应该很明显。
之所以没有提到常量，是因为复杂度的顺序更重要。一旦您知道算法是线性时间，您就可以在计算细节时自己检查斜率。
当您有两个程序时，O(n) 常量将决定哪个更好。然后你必须更详细地分析算法。