大O和等号，符号的滥用

Question

Wikipedia says：

语句 “F（x）是O（G（X））” 如上述所定义通常被写成 F（X）= O（G（X））。有些人认为这是对符号的滥用，因为 等号的使用可能会产生误导，因为它暗示了这种说法没有的对称性 。作为德布鲁因说，O（X）= O（X^2）是真实的，但O（X^2）= O（x）不是

我明白了正式的定义，但不是去熊先生说。我试图了解O（x）= O（x^2）甚至O（x）是O（x^2）的真实含义。

直觉上我会把它看作“具有复杂度x的函数类与具有复杂度x^2的函数类相同”。但这没有道理。

wikipedia talk页面也没有多大帮助。

Answer 1

直觉上我会把它看作“具有复杂度x的函数类与具有复杂度x^2的函数类相同”。但这没有道理。

是的，这就是为什么人们不喜欢带有等号的符号。

它应该被解读为“具有复杂度x的函数类别包含在具有复杂度x^2的函数类别”或“具有复杂度线性上限值的函数也是具有二次上部复杂度约束的函数“（当然，二次约束不是很紧）。

Answer 2

在数学中，'='通常表示“平等”，应该是equivalence relation。这意味着它应该是自反的，对称的和传递的。

当de Bruijn的说，O（X）= O（X^2）为真，但O（X^2）= O（x）是不

装置的关系不是对称。