) намного сложнее рассчитать.
=============================

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

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

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

 хотя они имеют похожее значение.

Обозначение Big-O f (n) = O (g (n)) означает, что f растет медленнее, чем g при больших значениях n ("n> n0"означает" для больших значений 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средний«Это учитывает только наиболее вероятные результаты. Таким образом, для быстрой сортировки f = O (n²) - лучшее, что вы можете получить, но fсредний = O (n log n).



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

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

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

То есть, в лучшем случае имеет место биг-О, Тета и Омега. То же самое касается среднего и худшего случая.

Смотрите также:[Как O и Ω относятся к худшему и лучшему случаям?](https://cs.stackexchange.com/questions/23068/how-do-o-and-%CE%A9-relate-to-worst-and-best-case)

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

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

Наилучший случай, когда он уже отсортирован, и в этом случае это займет линейное время, то есть`f(n) = k1n` время для некоторой константы`k1`.

`k1n` есть O (n), Θ (n), Ω (n). Согласно определениям, мы также можем сказать, что это O (n2) O (n3), ... или Ω (1), Ω (log n), Ω (log log n), ..., но обычно ожидается, что он представит самую узкую границу.

Худшие и средние случаи`g(n) = k2n2` а также`h(n) = k3n2`, которые оба O (n2), Θ (н2), Ом (n2).

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

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

Однако для некоторых алгоритмов сложно точно определить, что такое жесткая граница, в то время как легко получить верхнюю и / или нижнюю границу. Неоптимизированный алгоритм расчета[Числа Фибоначчи](https://en.wikipedia.org/wiki/Fibonacci_number) один такой пример - это не так уж сложно найти[верхняя граница O (2n)](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) а также[нижняя граница Ω (1,5n)](https://math.stackexchange.com/questions/571433/exponential-lower-bound-for-fibonacci-numbers), но жесткая граница ~ θ (1.6n) намного сложнее рассчитать.