Вычислительная сложность алгоритмов: удобная шпаргалка

Понимание вычислительной сложности алгоритмов важно для разработчика. Как минимум, про это могут спросить на собеседовании, как максимум — это поможет улучшить ваш проект.

Что это такое?

Вычислительная сложность пытается ответить: как изменятся время исполнения алгоритма и объём занятой памяти в зависимости от размера входных данных? Тут вводится понятие асимптотической сложности. Это математическая модель, описывающая поведение ограничений на ресурсы (например, время выполнения или использование памяти) в пределе, когда размер входных данных стремится к бесконечности. Алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных.

Для асимптотической сложности алгоритма используется следующая нотация: ?

(«О»-большое), которое описывает верхнюю границу времени.

Категории алгоритмической сложности в ?-нотации:

Постоянное время: ?(1)

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

Линейное время: ?(?)

Время выполнения пропорционально количеству элементов в наборе.

Логарифмическое время: ?(log?)

Время выполнения пропорционально логарифму от количества элементов в наборе.

Линейно-логарифмическое время: ?(?log?)

Время выполнения больше чем, линейное, но меньше квадратичного.

Квадратичное время: ?(?^2)

Время выполнения пропорционально квадрату количества элементов в наборе.

Ссылка на шпаргалку ? https://www.bigocheatsheet.com/

Источник: vk.com

Комментарии: