- Сложность алгоритма
- Количество шагов, необходимых для выполнения алгоритма, выраженное через размер входных данных.
- Асимптотическая сложность
- Функция, описывающая зависимость времени выполнения алгоритма от размера входных данных. Обычно выражается в Big O-нотации.
- Big O-нотация
- О-большое обозначение, используемое для описания верхней границы сложности алгоритма в худшем случае.
- О-большое ($O(f(n))$)
- Функция, которая растет не быстрее, чем $f(n)$, при $n$ стремящемся к бесконечности. Используется для оценки верхней границы сложности.
- О-малое ($o(f(n))$)
- Функция, растущая не медленнее, чем $f(n)$, при $n$ стремящемся к бесконечности. Используется для оценки нижней границы сложности.
- Theta-нотация ($\Theta(f(n))$)
- Функция, растущая с той же скоростью, что и $f(n)$, при $n$ стремящемся к бесконечности. Используется для точного описания сложности.
- Omega-нотация ($\Omega(f(n))$)
- Функция, растущая не медленнее, чем $f(n)$ и не быстрее, чем $c \cdot f(n)$ для некоторого положительного $c$. Используется для точной оценки сложности.
- Линейный алгоритм ($O(n)$)
- Алгоритм, сложность которого растет линейно с увеличением входных данных. Например, последовательный поиск.
- Квадратичный алгоритм ($O(n^2)$)
- Алгоритм, сложность которого растет квадратично с увеличением входных данных. Например, поиск в двумерном массиве.
- Экспоненциальный алгоритм ($O(2^n)$)
- Алгоритм, сложность которого растет экспоненциально с увеличением входных данных. Например, полный перебор.
- Неразрешимая задача ($NP$-полная)