В алгоритмической сложности омега большое обозначает лучший случай или нет?

Question

[MaxLich]

Здравствуйте. Читаю разные статьи и смотрю разные видео по алгоритмам и вычислении их сложности, и не могу понять: омега большое обозначает лучший случай или нет? В некоторых источниках лучший случай тоже обозначается О большим от какого выражения с n.

Answer 1

[ferasinka]

https://habrahabr.ru/post/188010/

О-большое — худший случай
Омега-большое — лучший случай
Тета-большое — когда худший и лучший случай одинаковы

Comments

[MaxLich]

Так как раз в этой статье всё обознается большим О: и лучший случай, и худший, и средний. Поэтому и непонятно.

Answer 2

[Labunsky]

Это не омега, это "О-большое". Грубо говоря - ограничение сверху. Алгоритм, имеющий сложность O(f(n)), при росте n будет расти (в плане времени работы) не быстрее, чем C*f(n) (C - константа)

UPD. Глаза мыльные, моя беда, ответ - да, "омега"-нотация обозначает лучший случай, О-большое - асимптотически худший

Comments

[MaxLich]

О большое - это же худший случай. Например, если это алгоритм сортировки массива по возрастанию. То лучший случай - когда он уже отсортирован по возрастанию. Худший случай - это когда он отсортирован по убыванию.
Из одной статьи: "Вообще, асимптотическая нотация для «худшего» случая называется O-нотацией, а для «лучшего» случая — омега (Ω)-нотацией."

[Labunsky]

MaxLich: это не "худший случай", потому что описывает лишь рост функции при росте ее аргумента, но никак не конкретные значения

То есть, пусть сложность алгоритма O(n^2). Это означает, что если мы будем брать поочередно n, увеличивая его постепенно, а время выполнения алгоритма будем рисовать на графике по точкам (абсцисса - n, ордината - время), то получится полу-парабола "вверх". Какая именно - да черт его знает, может, пологая, а может, вверх сразу устремится. Но мы заранее знаем, что каким бы оно там ни было вверху, отработает оно быстрее, чем, например, экспоненциальная функция. Или даже n^3

[Labunsky]

MaxLich: да, если там именно "омега" как символ - то это лучший случай. Глаза замылились, вижу О - читаю дальше как "О-большое")

[MaxLich]

Labunsky: А не можете тогда сказать, почему в хабре в этой статье всё обозначается как О большое?

[Labunsky]

MaxLich: потому что один и тот же алгоритм может иметь разные асимптотики в зависимости от входных данных. А О-большое для каждого такого варианта и обозначает худший случай

Грубо говоря, сортировка вставками отработает за линейное время на любом уже отсортированном массиве - то есть за О(n). И не изменится в зависимости от того, как этот отсортированный массив выглядит. А вот на отсортированных в обратном порядке она будет работать уже за O(n^2), опять же, вне зависимости от его внешнего вида

[MaxLich]

Labunsky: Не, я в смысле спрашиваю про то, почему в той статье и для худшого, и для лучшего, и для среднего случая используется нотация О большое.

[Labunsky]

MaxLich: потому что это разные "худшие случаи".
Там в таблицах, где разделяются случаи, имеется в виду "худший случай входных данных"
Асимптотика же там везде в таблицах указывает на "худший случай времени выполнения" алгоритма на соответствующем случае входных данных - поэтому и указана в О-нотации

[MaxLich]

Labunsky: То есть, например, при каким-то там хороших входных данных ("лучший случай" в статье) время выпонения будет расти не быстрее, например, О(n)?

[MaxLich]

Labunsky: То есть для лучших входных данных можно использовать и нотацию О большое? Не только Омегу большое?

[Labunsky]

MaxLich, ни то, ни другое, ты не правильно контекст уловил)
Смотри,

лучший случай для алгоритма имеет асимптотику O(nlog(n))

стоит читать как

алгоритм отработает в худшем случае за nlog(n) при условии, что входные данные будут наилучшими

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

[MaxLich]

Labunsky, Просто мне давали тестовое задание. И там надо было указать сложность написанного алгоритма. Я для худшего случая (в смыле данных) указал сложность с использованием O большое. Для лучшего случая входных данных я тоже указал сложность с использованием О большого. А теперь задумался, правильно ли это сделал. И поэтому сижу, разбираюсь, спрашиваю у всех про это. Так я был прав? (для лучшего случая в смысле входных данных)

[Labunsky]

MaxLich, правильно, то так и принято