为什么常量总是从大O分析中删除？ [英] Why is the constant always dropped from big O analysis?

问题描述

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

I'm trying to understand a particular aspect of Big O analysis in the context of running programs on a PC.

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

Suppose I have an algorithm that has a performance of O(n + 2). Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is O(n).

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

However, say another algorithm has an average performance of O(n² / 2). The book where I saw this example says the real performance is O(n²). I'm not sure I get why, I mean the 2 in this case seems not completely insignificant. So I was looking for a nice clear explanation from the book. The book explains it this way:

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

"Consider though what the 1/2 means. The actual time to check each value is highly dependent on the machine instruction that the code translates to and then on the speed at which the CPU can execute the instructions. Therefore the 1/2 doesn't mean very much."

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

And my reaction is... huh? I literally have no clue what that says or more precisely what that statement has to do with their conclusion. Can somebody spell it out for me please.

感谢您的帮助。

推荐答案

这些常量有意义还是有意义？和大O表示法是否关心它们？第二个问题的答案为否，而第一个问题的答案为绝对！

There's a distinction between "are these constants meaningful or relevant?" and "does big-O notation care about them?" The answer to that second question is "no," while the answer to that first question is "absolutely!"

Big-O表示法并不关心常量，因为big -O符号仅描述功能的长期增长率，而不是其绝对大小。将一个函数乘以一个常数只会对其常数的增长率产生影响，因此线性函数仍会线性增长，对数函数仍将对数增长，指数函数仍呈指数增长，等等。由于这些类别不受常数的影响，因此不会

Big-O notation doesn't care about constants because big-O notation only describes the long-term growth rate of functions, rather than their absolute magnitudes. Multiplying a function by a constant only influences its growth rate by a constant amount, so linear functions still grow linearly, logarithmic functions still grow logarithmically, exponential functions still grow exponentially, etc. Since these categories aren't affected by constants, it doesn't matter that we drop the constants.

也就是说，这些常量绝对是有效的！运行时间为10 ¹⁰⁰ n的函数将比运行时间仅为n的函数慢 way 。运行时间为n ² / 2的函数将比运行时间仅为n ² 的函数快。前两个函数都是O（n）而后两个函数都是O（n ² ）的事实并没有改变它们不在相同时间运行的事实，因为那不是big-O符号设计的目的。注记法对于确定从长远来看是否会大于另一个功能非常有用。即使10 ¹⁰⁰ n对于任何n> 0来说都是一个巨大的值，但该函数为O（n），因此对于足够大的n最终它将击败运行时间为n ^2的函数 / 2，因为该函数是O（n ² ）。

That said, those constants are absolutely significant! A function whose runtime is 10¹⁰⁰n will be way slower than a function whose runtime is just n. A function whose runtime is n² / 2 will be faster than a function whose runtime is just n². The fact that the first two functions are both O(n) and the second two are O(n²) doesn't change the fact that they don't run in the same amount of time, since that's not what big-O notation is designed for. O notation is good for determining whether in the long term one function will be bigger than another. Even though 10¹⁰⁰n is a colossally huge value for any n > 0, that function is O(n) and so for large enough n eventually it will beat the function whose runtime is n² / 2 because that function is O(n²).

总而言之，因为big-O只谈论相对类增长率，它忽略了恒定因素。但是，这些常数绝对重要。它们只是与渐进分析无关。

In summary - since big-O only talks about relative classes of growth rates, it ignores the constant factor. However, those constants are absolutely significant; they just aren't relevant to an asymptotic analysis.

希望这会有所帮助！

这篇关于为什么常量总是从大O分析中删除？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！