为什么常量总是从大 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 符号的设计目的.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屋！