Я считаю, что одной из самых сложных тем в карьере программиста является утверждение сложности алгоритма, поиск большого O и понимание того, что это такое. Даже профессиональным разработчикам или старшим инженерам-программистам всем нам может быть трудно понять это полностью.

Делаю свой собственный обзор сложности алгоритма и особенно Big O. Я поместил их все здесь, в этой статье, резюмируя их максимально простым способом.

Что такое Большое О?

Проще говоря, нотация Big O описывает сложность алгоритма в наихудшем сценарии.

Для получения дополнительной информации, нотация Big O — это математическая нотация, используемая для описания времени выполнения алгоритма с точки зрения размера входных данных в наихудшем сценарии.

С другой стороны, мы также можем видеть, что Big O буквально является верхней границей времени работы. Почему? Подробнее см. следующий абзац.

Вся картина нотаций

Может быть, некоторые из нас могут спросить, почему Big O является верхней границей времени работы, а не нижней? Что касается этого вопроса, я считаю, что некоторые из нас, включая меня, могли упустить всю картину.

В информатике у нас есть много видов обозначений:

Big Ω (большая нотация Omega) выражает меньшее время работы алгоритма, используемого для описания сценария наилучшего случая.

Big O (обозначение big O), выражает максимальное время работы алгоритма.

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

Кроме того, у нас также есть маленькие обозначения O, маленькие Ω.

В целом это объясняет, почему Big O является верхней границей времени работы алгоритма.

Почему наихудший случай имеет значение?

Почему производительность алгоритма подтверждается большим O, а не большим Ω?

В лучшем случае время работы разных алгоритмов обычно одинаково.

Например, в лучшем случае алгоритм двоичного поиска и алгоритм линейного поиска могут найти элемент X в массиве на самом первом шаге, независимо от размера входных данных, поэтому Big Ω равен 1. Разрыва почти нет, поэтому нет смысла утверждать об относительной эффективности между этими алгоритмами в лучшем случае.

Наоборот, в худшем случае время работы алгоритма сильно отличается. Это O(log N), O(N) относительно бинарного поиска и линейного поиска. Разница во времени работы очевидна, поэтому мы можем легко найти лучший алгоритм.

Найдите большое O алгоритма

Шаги определения сложности алгоритма перечислены ниже:

Шаг 1. Определите входные данные, которые повлияют на время работы алгоритма.

Обычно это (n) размер массива и (x) элемент, который мы находим.

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

Обычно это цикл for, который перебирает массив.

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

Например, в алгоритме со временем выполнения O(n² + n) доминирующим членом является n². По мере увеличения размера входных данных время работы алгоритма будет экспоненциально увеличиваться из-за члена n², а член n будет оказывать все меньшее и меньшее влияние на общее время выполнения. Следовательно, O (n²) является доминирующим членом

Вот и все

Это то, что есть, в Интернете есть много ресурсов на эту тему. Тем не менее, я надеюсь, что то, что я подытожу, поможет вам взглянуть на эту тему с другой точки зрения и развеять ваши сомнения.

Далее я планирую продолжить развивать эту тему с некоторыми примерами поиска большого O алгоритма, так что следите за обновлениями.