大O和等号,滥用符号 [英] Big-O and equals sign, abuse of notation
问题描述
上面定义的语句"f(x)是O(g(x))"通常写为 f(x)= O(g(x)).有些人认为这是对符号的滥用,因为 使用等号可能会引起误解,因为这表明 该语句没有的对称性.正如德布赖恩所说,O(x)= O(x ^ 2)是真实的,但O(x ^ 2)= O(x)不是
The statement "f(x) is O(g(x))" as defined above is usually written as f(x) = O(g(x)). Some consider this to be an abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As de Bruijn says, O(x) = O(x^2) is true but O(x^2) = O(x) is not
我理解正式的定义,但不明白德布鲁因所说的.试图理解O(x)= O(x ^ 2)甚至O(x)是O(x ^ 2)的真正含义使我感到困惑.
I understand the formal definition but not what de Bruin says. Im puzzeled by trying to understand what O(x) = O(x^2) or even O(x) is O(x^2) really means.
直觉上,我将其理解为复杂度为x的函数的类与复杂度为x ^ 2的函数的类相同".但这没有道理.
Intuitively I would read it as "The class of functions with complexity x is the same as the class of functions with complexity x^2". But that does not make sense.
维基百科讨论页没有帮助要么很多.
The wikipedia talk page does not help much either.
推荐答案
直觉上,我将其理解为复杂度为x的函数的类与复杂度为x ^ 2的函数的类相同".但这没有道理.
Intuitively I would read it as "The class of functions with complexity x is the same as the class of functions with complexity x^2". But that does not make sense.
是的,这就是为什么人们不喜欢带有等号的符号的原因.
Yes, and that is why people don't like the notation with the equals sign.
应读为复杂度为x ^ 2的函数类中包含复杂度为x的函数类"或复杂度为线性上限的函数也是复杂度为二次函数上限的函数" (当然,二次边界不是很严格).
It should read as "The class of functions with complexity x is included in the class of functions with complexity x^2" or "A function with a linear upper bound for complexity is also a function with a quadratic upper complexity bound" (where of course the quadratic bound is not very tight).
这篇关于大O和等号,滥用符号的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!