Для оценки сложности алгоритма используют асимптотический анализ, который позволяет описать эффективность алгоритма в зависимости от размера входных данных ( $n$ ). Основные шаги:

Определение базовых операций: Выделяются операции, время выполнения которых существенно зависит от $n$ (например, сравнения, присваивания, арифметические операции).
Подсчет числа операций: Вычисляется количество базовых операций в зависимости от $n$ . Это может быть точная формула или оценка.
Определение асимптотического класса: Используются обозначения Большого О ( $O$ ), Омега ( $\Omega$ ) и Тета ( $\Theta$ ) для описания верхнего, нижнего и точного асимптотического поведения соответственно.

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

Наиболее часто используется Большое $O$ для описания верхней границы времени выполнения, что важно для понимания масштабируемости алгоритма в наихудшем сценарии.

Пренебрежение константами и младшими членами: При определении асимптотики игнорируются константные множители и члены более низкого порядка, так как при больших $n$ доминирует функция с наибольшим показателем. Например, для $3n^2 + 5n + 10$ , асимптотика будет $O(n^2)$ .

Типичные асимптотические классы (в порядке возрастания сложности):

$O(1)$ : Константная сложность (время выполнения не зависит от $n$ ).
$O(\log n)$ : Логарифмическая сложность (время выполнения растет очень медленно с ростом $n$ , характерно для алгоритмов бинарного поиска).
$O(n)$ : Линейная сложность (время выполнения прямо пропорционально $n$ , характерно для простого перебора).
$O(n \log n)$ : Линейно-логарифмическая сложность (характерно для эффективных алгоритмов сортировки, таких как Quick Sort или Merge Sort).
$O(n^2)$ : Квадратичная сложность (время выполнения растет с квадратом $n$ , характерно для простых алгоритмов сортировки, таких как Bubble Sort).
$O(n^c)$ (для $c > 1$ ): Полиномиальная сложность.
$O(c^n)$ (для $c > 1$ ): Экспоненциальная сложность (время выполнения растет очень быстро с ростом $n$ , характерно для перебора всех возможных вариантов).
$O(n!)$ : Факториальная сложность (самый высокий класс сложности, растет чрезвычайно быстро).

Для определения асимптотики циклических структур:

Последовательные блоки кода: Складывается сложность блоков. $O(A+B) = O(\max(A, B))$ .
Вложенные циклы: Перемножается количество итераций циклов. Цикл с $n$ итерациями, внутри которого другой цикл с $m$ итерациями, имеет сложность $O(n \times m)$ . Если $m=n$ , сложность $O(n^2)$ .
Циклы с уменьшением размера входных данных: Например, деление на 2 на каждой итерации приводит к логарифмической сложности ( $O(\log n)$ ).

Пример:

Простой перебор массива:

python

Если размер массива $n = \texttt{len(arr)}$ , цикл выполняется $n-1$ раз. В каждой итерации выполняется константное число операций. Общее число операций пропорционально $n$ . Асимптотическая сложность: $O(n)$ .

Пример: Сортировка вставками (Insertion Sort)

python

Внешний цикл выполняется $n-1$ раз. Внутренний цикл в наихудшем случае (массив отсортирован в обратном порядке) выполняется в среднем $i/2$ раз (или до $i$ раз). Суммарно по всем итерациям внешнего цикла количество операций во внутреннем цикле: $1 + 2 + ... + (n-1) \approx n^2/2$ . Асимптотическая сложность: $O(n^2)$ в наихудшем и среднем случаях, $O(n)$ в наилучшем случае (массив уже отсортирован). При оценке сложности обычно подразумевают наихудший случай (Большое $O$ ).

Как произвести оценку сложности алгоритма или определить асимптотику?