Трудность в понимании асимптотической записи

Question

Насколько я знаю и исследования,

Большой - О нотация описывает наихудший случай сложности времени алгоритма.

Big - Omega нотация описывает лучший случай сложности времени алгоритма.

Big - тета-нотация описывает средний случай сложности алгоритма по времени.

Источник

Однако в последние дни я видел дискуссию, в которой некоторые ребята рассказывают, что

O в худшем случае - это «простительное» заблуждение. Θ для лучшего это просто неправильно. Ω для лучшего тоже простительно. Но они остаются заблуждением.

Обозначение big-O может представлять любую сложность. На самом деле это может опишите асимптотическое поведение любой функции.

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

Answer 1

Эти утверждения в лучшем случае неточны, а в худшем неверны.Вот истина.

• Время выполнения алгоритма составляет , а не функция N (так как это также зависит от конкретного набора данных), поэтому вы не можетеобсудить его асимптотическую сложность напрямую.Все, что вы можете сказать, это то, что он лежит между лучшим и худшим случаями.

• Время выполнения в наихудшем, наилучшем и среднем случаях зависит от N, хотя среднее значение зависит отвероятностное распределение данных, поэтому не определяется однозначно.

Тогда асимптотическая запись такова, что

• O (f (N))обозначает верхнюю границу, которая может быть жесткой или нет;

• Ом (f (N)) обозначает нижнюю границу, которая может быть жесткой или нет;

• Θ (f (N)) обозначает двустороннюю границу, т. Е. Соединение O (f (N)) и Ω (f (N));она жесткая.

Итак,

• Все сложности наихудшего случая, лучшего случая и среднего случая имеют Θ-пределтак как они являются функциями;на практике эту границу может быть слишком сложно установить, и вместо этого мы ограничиваемся более свободными границами O или Ω.

• Абсолютно неверно, что граница reserved зарезервирована для среднего случая.

Примеры:

Наихудшим случаем быстрой сортировки является Θ (N²), а его лучшим и средним значениями являются Θ (N Log N).Таким образом, из-за злоупотребления языком , время быстрой сортировки составляет O (N²) и Ω (N Log N).

Наихудший, лучший и средний случаи сортировки при вставкевсе три Θ (N ²).

Любой алгоритм, который должен смотреть на все входные данные, Ω (N) для наилучшего, среднего и наихудшего случая (и без дополнительной информации мы не можем определить верхний регистр).связанный).

Известно, что умножение матриц возможно во время O (N³).Но мы все еще не знаем точно Θ границы этой операции, которая в N × раз является медленно растущей функцией.Таким образом, Ω (N²) является очевидной, но не жесткой нижней границей.(Худшие, лучшие и средние дела имеют одинаковую сложность.)

---

Существует некоторая путаница, связанная с тем, что лучшие / средние / худшие случаи имеют четко определенные длительности, тогда как общий случай заключается вдиапазон (это на самом деле случайная величина).Кроме того, анализ алгоритмов часто утомителен, если не труден, и мы используем упрощения, которые могут привести к неопределенности.

Answer 2

Нотация Бахманна-Ландау не имеет абсолютно никакого отношения к вычислительной сложности алгоритмов.Это уже должно быть очень очевидным из-за того, что идея вычислительной машины, которая вычисляет алгоритм, в действительности не существовала в 1894 году, когда Бахман и Ландау изобрели эту нотацию.

Нотация Бахманна-Ландау описывает темпы ростафункций, сгруппировав их в наборы функций, которые растут примерно с одинаковой скоростью.Обозначения Бахманна-Ландау ничего не говорят о том, что означают эти функции.Они просто функции.На самом деле, они вообще ничего не должны значить.

Все, что они имеют в виду, это:

• f ∈ ο (g): f растет медленнее, чем g
• f ∈ Ο (g): f не растет значительно быстрее, чем g
• f ∈ Θ (g): f растет так же быстро, как g
• f ∈ Ω (g): f не растет значительно медленнее, чем g
• f ∈ ω (g): f растет быстрее, чем g

Это ничего не говорит о том, что такое f или g, иличто они означают.

Обратите внимание, что на самом деле существует два противоречивых, несовместимых определения Ω;Один из приведенных здесь является более полезным для теории сложности вычислений.Также обратите внимание, что это только очень широкие интуиции, когда вы сомневаетесь, вы должны посмотреть на определения.

Если вы хотите, вы можете использовать нотацию Бахмана-Ландау для описания скорости роста популяции кроликов какфункция времени или скорость роста человеческого живота как функция пива.

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