为什么常量总是从大O分析中删除？

Question

我试图了解在PC上运行程序的背景下Big O分析的特定方面。

假设我有一个性能为O（n + 2）的算法。在这里，如果n真的很大，则2变得无关紧要。在这种情况下，很明显，实际性能为O（n）。

但是，可以说另一种算法的平均性能为O（n ^ 2/2）。在我看到该示例的书中，实际表现为O（n ^ 2）。我不确定为什么，我的意思是在这种情况下2似乎并不完全无关紧要。因此，我一直在从书中寻找清晰的解释。这本书是这样解释的：

“虽然要考虑1/2的含义。检查每个值的实际时间高度取决于代码转换成的机器指令，然后取决于CPU执行指令的速度。因此1/2并不正确。不是很重要。”

我的反应是……嗯？我从字面上不知道所说的是什么，或更确切地说，该陈述与他们的结论有什么关系。有人可以帮我拼一下吗。

谢谢你的帮助。

Answer 1

“这些常量有意义还是相关？”之间有区别。和“大O表示法是否关心它们？” 第二个问题的答案为“否”，而第一个问题的答案为“绝对！”。Big-O表示法并不关心常量，因为big-O表示法仅描述函数的长期增长率，而不是函数的绝对值。将一个函数乘以一个常数只会对其常数的增长率产生影响，因此线性函数仍会线性增长，对数函数仍将对数增长，指数函数仍呈指数增长，等等。由于这些类别不受常数的影响，因此不会无论我们删除常数。也就是说，这些常量绝对重要！的函数，其运行时间为10 100 n将被方式比其运行时只是N A功能慢。运行时间为n 2/2的函数将比运行时间仅为n 2的函数快。前两个函数均为O（n）且后两个函数均为O（n 2）的事实并没有改变它们不在相同时间段内运行的事实，因为这不是big-O表示法专为。O标记法对于确定一个功能在长期内是否会大于另一个功能非常有用。尽管10 100对于任何n> 0，n都是一个巨大的值，该函数为O（n），因此对于足够大的n最终，它将击败运行时间为n 2/2的函数，因为该函数为O（n 2）。综上所述-由于big-O仅谈论增长率的相对类别，因此它忽略了恒定因素。但是，这些常数绝对重要。它们只是与渐进分析无关。希望这可以帮助！