Big-O и знак равенства, злоупотребление обозначениями

Question

Википедия говорит :

Утверждение "f (x) равно O (g (x))", как определено выше, обычно записывается как f (x) = O(г (х)).Некоторые считают, что это злоупотребление нотацией, поскольку использование знака равенства может вводить в заблуждение, поскольку предполагает симметрию, которой нет в этом утверждении.Как говорит де Брюйн, O (x) = O (x ^ 2) верно, но O (x ^ 2) = O (x) не

Я понимаю формальное определение, но не то, что деБрюин говорит.Я озадачен, пытаясь понять, что O (x) = O (x ^ 2) или даже O (x) означает O (x ^ 2) на самом деле.

Интуитивно я бы прочитал это как «Классфункции со сложностью x такой же, как и класс функций со сложностью x ^ 2 ".Но это не имеет смысла.

Страница 1013 * wikipedia talk также не сильно помогает.

Answer 1

Интуитивно я бы прочитал его как «Класс функций со сложностью x такой же, как класс функций со сложностью x ^ 2». Но это не имеет смысла.

Да, и именно поэтому людям не нравятся обозначения со знаком равенства.

Следует читать как «Класс функций со сложностью x включен в класс функций со сложностью x ^ 2» или «Функция с линейной верхней границей сложности также является функцией с квадратичной верхней границей сложности» (где, конечно, квадратичная граница не очень тесная).

Answer 2

В математике обычно ожидается, что '=' представляет "равенство", и должно быть отношением эквивалентности . Это означает, что он должен быть рефлексивным, симметричным и транзитивным.

Как говорит де Брюйн, O (x) = O (x ^ 2) верно, но O (x ^ 2) = O (x) не

означает, что отношение не симметрично.