为什么总是不断从大O分析少了？ [英] Why is constant always dropped from big O analysis?

问题描述

我想了解大O分析的特定方面在PC上运行的程序的情况下。

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

假设我有一个算法，具有邻性能（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/2）的平均业绩。这本书在那里我看到这个例子说，真正的性能是O（n ^ 2）。我不知道我知道为什么，我的意思是在这种情况下，2似乎没有完全微不足道。所以我一直在寻找的书一个不错的明确的解释。书中这样解释：

However, say another algorithm has an average performance of O(n^2/2). The book where I saw this example says the real performance is O(n^2). 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的手段，实际时间来检查每个值   高度依赖于机器指令，该code   转化为然后在在此，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."

和我的反应是......咦？？？我真的不知道什么，说以上precisely什么声明，是因为有他们的结论。有人可以拼出来，我请。

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符号并不关心常量，因为大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的函数慢。它的运行时间是一个函数为n ² / 2会比它的运行时间是仅仅局限于N ² 函数更快。事实上，前两个功能均为O（n）和第二两个是为O（n ² ）不会改变的事实，他们没有在相同时间内运行，因为这不是什么大O记法是专为。 O符号是很好的确定是否的在长期的一个函数将大于其它。尽管10 ¹⁰⁰ n是任意n> 0 colossally巨大的价值，该功能是O（n）等足够大的n最终会战胜它的运行时间是函数为n ² / 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²).

在总结 - 因为大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屋！