大 O 和等号，滥用符号
上面定义的语句“f(x) is O(g(x))”通常写为 f(x) = O(g(x))。有些人认为这是对符号的滥用，因为 使用等号可能会产生误导，因为它表明 该陈述不具有对称性。正如 de Bruijn 所说，O(x) = O(x^2) 为真，但 O(x^2) = O(x) 为假
我理解正式定义，但不理解 de Bruin 所说的。我对试图理解 O(x) = O(x^2) 甚至 O(x) is O(x^2) 的真正含义感到困惑。
直觉上我会把它理解为“复杂度为 x 的函数类与复杂度为 x^2 的函数类相同”。但这没有意义。
维基百科讨论页面也没有多大帮助。
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
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，这就是为什么人们不喜欢等号符号的原因。
它应该读作“复杂性为 x 的函数类包含在复杂性为 x^2 的函数类中”或“具有线性复杂性上限的函数也是具有二次复杂性上限的函数”（其中当然二次界不是很紧）。
Yes, and that is why people don't like the notation with the equals sign.
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).
在数学中，“=”通常代表“相等”，并且应该是等价关系。这意味着它应该是自反的、对称的和传递的。
意味着关系不对称。
In math, '=' is usually expected represent "equality", and should be an equivalence relation. This means it should be reflexive, symmetric and transitive.
means the relation is not symmetric.