Оценка сложности алгоритмов

dlyachainikov.ru · Программирование

Сложность алгоритма

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

Виды сложности

Асимптотическая верхняя граница сложности: обозначается как O(f(n)), где f(n) – функция, описывающая максимальное время работы алгоритма.
Асимптотическая нижняя граница сложности: обозначается как Ω(g(n)).

Линейная сложность

$T(n) = n$
Сложность: $O(n)$

Логарифмическая сложность

$T(n) = \log_2{n}$
Сложность: $O(\log n)$

Квадратичная сложность

$T(n) = n^2$
Сложность: $O(n^2)$

Пример анализа алгоритма

Время выполнения этого алгоритма зависит от длины массива и составляет $O(n)$ , так как каждая операция выполняется ровно один раз для каждого элемента массива.

Пропуски для самопроверки

асимптотическаяверхняяграницасложности методбольшогомалогоомега логарифмическаясложность квадратичнаясложность

Сложность алгоритма

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

Виды сложности

Асимптотическая верхняя граница сложности: обозначается как O(f(n)), где f(n) – функция, описывающая максимальное время работы алгоритма.

Асимптотическая нижняя граница сложности: обозначается как Ω(g(n)).