ビッグ-Oおよび記号表記

Question

Wikipedia saysの乱用等しい：上記で定義したステートメント

"をf（x）はO（G（x））がある" は、通常 F（X）=のように書かれていますO（g（x））である。 等号の使用は、このステートメントにはない の対称性を示唆しているので、これを誤認する可能性があるため、これを表記の悪用とみなす人もいます。デBruijnグラフが言うように、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の関数のクラスに含まれています"または "複雑さのための線形の上限を持つ関数もまた、 "（もちろん2次境界はあまり緊密ではない）。

Answer 2

数学では、 '='は通常 "等価"を表すと予想され、equivalence relationである必要があります。つまり、反射的、対称的、推移的でなければなりません。デBruijnグラフが言うよう

、O（X）= O（X^2）は真であるが、O（X^2）= O（x）は

ない

は関係が対称ではないことを意味します。