Сложность алгоритма и O-нотация

Сложность алгоритма — это оценка того, как растут затраты алгоритма (время выполнения или объём памяти) при увеличении размера входных данных. Она позволяет сравнивать алгоритмы между собой независимо от конкретного компьютера, языка или компилятора: важно не сколько миллисекунд занял запуск, а как быстро растёт число операций, когда данных становится больше.

Асимптотическая сложность и O-нотация

Асимптотическая сложность — это поведение алгоритма при стремлении размера входных данных n к бесконечности. На малых данных даже неэффективный алгоритм работает быстро, поэтому нас интересует именно тенденция роста на больших n.

Для описания этой тенденции используют O-нотацию (читается «O-большое», по-английски Big O). Запись O(f(n)) означает, что число операций растёт не быстрее, чем функция f(n), с точностью до постоянного множителя. Например, O(n) — линейный рост: удвоили данные — примерно удвоилось время; O(n^2) — квадратичный: удвоили данные — время выросло вчетверо.

Основные классы сложности

Чаще всего встречаются следующие классы сложности (перечислены от самого быстрого к самому медленному):

Наглядно разницу в скорости роста показывают графики: чем «круче» кривая, тем хуже алгоритм масштабируется.

Примеры на Java по классам

O(1) — константная. Число операций не зависит от размера массива: обращение по индексу выполняется за один шаг.

int first(int[] arr) {
    return arr[0]; // одна операция независимо от длины массива
}

O(n) — линейная. Один цикл по всем элементам: чем больше массив, тем больше итераций.

int sum(int[] arr) {
    int total = 0;
    for (int value : arr) { // n итераций
        total += value;
    }
    return total;
}

O(log n) — логарифмическая. Бинарный поиск на каждом шаге отбрасывает половину диапазона, поэтому число шагов растёт как логарифм от n.

int binarySearch(int[] sorted, int key) {
    int low = 0, high = sorted.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (sorted[mid] == key) return mid;
        if (sorted[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

O(n log n) — квазилинейная. Такую сложность имеют эффективные сортировки. В Java для этого достаточно вызвать Arrays.sort:

int[] data = {5, 2, 8, 1, 9};
java.util.Arrays.sort(data); // сортировка за O(n log n)

O(n^2) — квадратичная. Вложенный цикл: для каждого из n элементов выполняется ещё n действий.

void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {        // n раз
        for (int j = 0; j < arr.length; j++) {    // и ещё n раз
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

O(2^n) — экспоненциальная. Наивное рекурсивное вычисление чисел Фибоначчи каждый раз порождает два вызова, поэтому число операций удваивается с ростом n.

long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2); // два вызова на каждый шаг
}

Правила подсчёта O-большого

Чтобы привести выражение к нотации O-большого, применяют несколько правил:

• Константы-множители отбрасываются — они не влияют на порядок роста:

  8n^4 = O(n^4),   (n^2)/5 = O(n^2)

• Учитывается только самый быстрорастущий член — при большом n остальные слагаемые становятся пренебрежимо малы:

  n^2 + n = O(n^2),   2^n + n^9 = O(2^n)

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

• Последовательные блоки складываются, вложенные — перемножаются. Два цикла подряд дают O(n) + O(n) = O(n), а цикл внутри цикла — O(n) × O(n) = O(n^2).

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

Сложность оценивают по двум ресурсам:

• Временная сложность (time complexity) — как растёт число операций, то есть время выполнения.
• Пространственная сложность (space complexity) — как растёт объём дополнительной памяти, которую алгоритм использует помимо самих входных данных.

Эти оценки не обязаны совпадать. Например, алгоритм может работать за O(n) по времени, но требовать лишь O(1) дополнительной памяти (обходит массив, храня только счётчик). Часто между ними приходится искать компромисс: ускорение за счёт кэширования результатов увеличивает расход памяти.

Худший, средний и лучший случай

Один и тот же алгоритм может отработать по-разному в зависимости от входных данных. Поэтому различают три оценки:

• Худший случай — верхняя граница, обозначается O-большим. Именно её обычно приводят, потому что она гарантирует, что медленнее не будет.
• Средний случай — типичное поведение на случайных данных (Θ, «тета-большое»).
• Лучший случай — нижняя граница (Ω, «омега-большое»).

Пример: линейный поиск элемента в массиве в лучшем случае находит его сразу — O(1), а в худшем проходит весь массив — O(n). Когда говорят «сложность линейного поиска — O(n)», имеют в виду именно худший случай.

Как определить сложность на практике

Простой ориентир для быстрой оценки кода:

• Нет циклов, только простые операции и обращения по индексу — O(1).
• Один цикл по данным — O(n).
• Цикл внутри цикла по тем же данным — O(n^2); три вложенных — O(n^3).
• На каждом шаге диапазон делится пополам (бинарный поиск, обход сбалансированного дерева) — O(log n).
• Цикл, внутри которого выполняется деление данных пополам, или эффективная сортировка — O(n log n).
• Рекурсия, которая на каждом шаге порождает несколько вызовов над почти тем же объёмом данных, — часто O(2^n).

Где чаще всего путаются

• Считают, что O-большое — это точное время. Это порядок роста, а не число секунд; константы намеренно отброшены.
• Забывают, что O(1) не значит «мгновенно». Это значит «не зависит от размера данных», но сама операция может быть тяжёлой.
• Не замечают скрытые циклы. Вызов вроде list.contains(x) внутри цикла добавляет ещё O(n), превращая проход в O(n^2).
• Путают сложность структуры данных и операции. У ArrayList доступ по индексу — O(1), а вставка в начало — O(n); у HashMap поиск в среднем O(1), но в худшем случае может деградировать.