Определение нотации Big-O

Question

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

O: наихудший случай обозначения Big-O.
Θ: средний случай тета-записи.
Ω: наилучший случай записи омега

Почему Википедия представляет скорость алгоритмов только в Big-O, включая ее средний, лучший и худший случаи?Почему они не заменили эти формальные ключевые слова?

Answer 1

O, Θ и Ω не представляют наихудший, средний и лучший случай; хотя они имеют похожее значение.

Обозначение Big-O f (n) = O (g (n)) означает, что f растет медленнее, чем g для больших значений n («n> n ₀ » означает «для больших значений n» " в данном контексте). Это не означает, что g - наихудший случай: g может быть хуже, чем наихудший случай (например, быстрая сортировка также O (n!)). Для более сложных алгоритмов ведутся исследования по определению наименьшего Big-O для их реальной сложности: автор в основном находит верхнюю границу Big-O.

Обозначение Ω означает обратное (f растет быстрее, чем g), что означает, что оно может быть лучше, чем в лучшем случае (например, все алгоритмы имеют Ω (1)).

Существует много алгоритмов, для которых не существует единственной функции g, такой, чтобы сложность была и O (g), и Ω (g). Например, сортировка вставки имеет нижнюю границу Big-O, равную O (n²) (то есть вы не можете найти ничего меньше n²), и верхнюю границу Ω (n).

Другие алгоритмы: сортировка слиянием - это O (n log n) и Ω (n log n). Когда это происходит, оно записывается как Θ (n log n), что означает, что не все алгоритмы имеют сложность Θ-нотации (и, в частности, алгоритмы с наихудшими или лучшими случаями не имеют таковых).

Чтобы избавиться от наихудших случаев, которые имеют очень низкую вероятность, достаточно часто исследовать сложность среднего случая - заменяя стандартное значение "f" в левой части другой функцией "f _avg", который учитывает только наиболее вероятные результаты. Таким образом, для быстрой сортировки f = O (n²) - лучшее, что вы можете получить, но f _avg = O (n log n).

Answer 2

Я не уверен, где вы нашли эти определения, но я бы посчитал их неправильными.

В лучшем, среднем и худшем случаях все функции, как правило, превышают размер ввода.

Big-O, Theta и Omega указывают, соответственно, верхнюю, жесткую и нижнюю границы любой заданной функции.

То есть в лучшем случае имеет предел big-O, Theta и Omega.То же самое касается среднего и наихудшего случая.

См. Также: Как соотносятся O и Ω с наихудшим и лучшим случаем?

Примечание: обычно используется big-O(возможно, неправильно) используется для обозначения жесткой границы (вместо тета).

---

Давайте рассмотрим пример сортировки вставкой.

Наилучший случай - это когда сортировка уже выполнена, в которойЕсли это займет линейное время, то есть f(n) = k<sub>1</sub>n время для некоторой постоянной k<sub>1</sub>.

k<sub>1</sub>n - это O (n),, (n), Ω (n).Согласно определениям, мы также можем сказать, что это O (n ² ), O (n ³ ), ... или Ω (1), Ω (log n), Ω(log log n), ..., но обычно ожидается, что он представит самую жесткую границу.

Наихудшим и средним значениями являются g(n) = k<sub>2</sub>n<sup>2</sup> и h(n) = k<sub>3</sub>n<sup>2</sup>, которые оба равны O (n ²), Θ (n ² ), Ω (n ² ).

---

Теперь вы можете сказать: это не очень полезнозачем нам три границы, если они всегда одинаковы?Почему бы нам не использовать тэту везде?

В общем, вы были бы абсолютно правы - алгоритмы часто описываются в терминах только одной из границ (обычно это жесткая граница).

Однако для некоторых алгоритмов сложно точно определить, что такое жесткая граница, в то время как легко получить верхнюю и / или нижнюю границу.Неоптимизированный алгоритм вычисления чисел Фибоначчи является одним из таких примеров - нетрудно найти верхнюю границу O (2 ⁿ ) и aнижняя граница Ω (1,5 ⁿ ) , но жесткую границу ~ θ (1,6 ⁿ ) вычислить гораздо сложнее.