Для оценки сложности алгоритма используют асимптотический анализ, который позволяет описать эффективность алгоритма в зависимости от размера входных данных ($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)$).

Пример:

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

# Пересчет базовых операций (сравнения, присваивания)
# В данном случае, основная операция - сравнение в цикле
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 присваивание (вне цикла)
    for i in range(1, len(arr)): # Цикл выполняется len(arr) - 1 раз
        # Внутри цикла:
        # 1 сравнение (if arr[i] > max_val)
        # potentially 1 присваивание (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

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

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

# Пересчет базовых операций
# Основные операции: сравнения и присваивания/перемещения элементов
def insertion_sort(arr):
    # Внешний цикл выполняется n-1 раз
    for i in range(1, len(arr)):
        key = arr[i] # 1 присваивание
        j = i - 1 # 1 присваивание
        # Внутренний цикл выполняется в худшем случае i раз
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 присваивание (перемещение)
            j -= 1 # 1 вычитание и 1 присваивание
        arr[j + 1] = key # 1 присваивание

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

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