Ожидаемый синтаксис для обозначения Big O

Question

Есть ли ограниченное количество базовых нотаций, если учесть, что вы должны «перевести» их в самую важную часть?

O (n ^ 2):

O (n):

O (1):

O (log n) логарифмический

O (n!) Факториал

O (na) полином

Или от вас ожидают разработки таких вариаций, как O (n ^ 4) и т. Д. ... и если да,это единственное исключение?сила Х один?

Answer 1

Как правило, вы перегоняете нотацию Big-O (и связанные нотации Бахмана-Ландау, такие как Big-Theta и Big-Omega) вплоть до операции быстро растущего N-члена.Таким образом, вы удаляете / упрощаете меньшие члены (N ² + N == O (N ² )) и неизменяемые коэффициенты члена ( O (4N ² ) == O (N ² )), но НЕ являются степенями или основаниями экспонент ( O (3 ^4N ) == O (3 ^N )).Вы также не снимаете переменные коэффициенты;NlogN - это NlogN, НЕ logN или N.

Таким образом, вы обычно будете видеть числа в нотации Big-Oh только в том случае, если сложность является полиномиальной (степень N) или экспоненциальной (N-я степень основания).Наиболее распространенные нотации Big-Oh очень похожи на те, которые вы показываете, с добавлением NlogN (ОЧЕНЬ распространено).

Однако, если вы различаете два алгоритма одинаковой общей сложности, вы МОЖЕТЕ добавить меньшие термины и /или коэффициенты обратно, чтобы продемонстрировать относительную разницу;алгоритм, который выполняет линейно, но имеет двойные инструкции другого, может быть описан как O (2N) при сравнении его с другим O (N) алгоритмом.Однако, взятые по отдельности, оба алгоритма являются линейными ( O (N)).

Некоторые обозначения Big-O не являются алгебраическими и могут включать несколько переменных в простейшей форме общего случая.Например, сортировкой счета является сложность O (Макс (N, M)), где N - количество элементов в списке, а M - диапазон этих элементов.Часто это можно уменьшить в определенных случаях, определив M в терминах N и, таким образом, сократив до одной переменной (если рассматриваемый список состоит из первых N квадратов, M = N ² -1), но в общем случае обе переменные независимы и значимы.Официально сложность BucketSort составляет O (N), но на самом деле это больше похоже на O (NlogM), где M - максимальное значение из списка из N элементов.M обычно считается незначительным, но это зависит от значений, которые вы обычно сортируете (для сортировки 5 значений каждое на миллиарды потребуется больше циклов для сравнения каждой степени 10, чем обходы по списку, чтобы поместить их в сегменты) и от используемого радиуса(RadixSort - это BucketSort с базовым значением 2; опять же, для сортировки значений с большим значением log ₂ потребуется больше циклов, чем обходов).

Answer 2

Нет, число различных O-классов не является конечным.

Как вы уже упоминали, O (n ^ x) описывает разные наборы для каждого x.И это не единственное «исключение».O (x ^ n) также различный набор для каждого x.Точно так же O (n ^ n), O (n ^ n ^ n), O (n ^ n ^ n ^ n) и т. Д. Являются различными наборами (и вы, конечно, можете продолжать это до бесконечности).

Answer 3

Нотация Big-O - это способ обеспечить верхнюю границу ограничивающего поведения функции. Нет никаких ограничений по его функциональной форме. Тем не менее, существуют определенные соглашения, как объяснено Wikipedia :

При типичном использовании формальное определение нотации O не используется напрямую; скорее, обозначение O для функции f (x) получено по следующим правилам упрощения:

• Если f (x) является суммой нескольких слагаемых, то значение с наибольшим темпом роста сохраняется, а все остальные опускаются.
• Если f (x) является произведением нескольких факторов, любые константы (члены в произведении, не зависящие от x), опускаются.

Конечно, существуют некоторые функциональные формы, которые обнаруживаются чаще, чем другие. Некоторые общие классы перечислены здесь .

Answer 4

Как правило, вы делите выражение на сумму произведений, сохраняете наибольший член и делите его на константы, чтобы максимально упростить его.

ex:

n (2n+ 3log (n)) => 2n ^ 2 + 3nlog (n) => 2n ^ 2 => n ^ 2

(n + 1) (2nlog (n) + n) => 2n ^ 2log(n) + n ^ 2 + 2nlog (n) + n => 2n ^ 2log (n) => n ^ 2log (n)