Временная сложность алгоритма

Описание	В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
Область знаний	Информатика
Авторы
Поясняющее видео
Близкие понятия
Среды и средства для освоения понятия	R, J, Python, Snap!

Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.

Название	Примеры алгоритмов
константное время	Определение чётности целого числа (представленного в двоичном виде)
логарифмическое время	Двоичный поиск
линейное время	Поиск наименьшего или наибольшего элемента в неотсортированном массиве
экспоненциальное время (с линейной экспонентой)	Решение задачи коммивояжёра с помощью динамического программирования
экспоненциальное время
факториальное время