Сложность алгоритма: как оценить O(n) и зачем это спрашивают

Как считать операции, что значат O(n), O(n²) и O(log n), сложность сортировок и памяти и как прикинуть, уложится ли решение в лимит времени.

На экзамене просят «оценить сложность», на автопроверке решение получает Time Limit Exceeded, хотя на примере из условия отработало мгновенно. Обе ситуации про одно: как растёт время работы, когда растут входные данные. Ниже разберём, как считать операции, что на самом деле значит O(n), где прячутся лишние циклы и как до отправки прикинуть, уложится ли решение в секунду. Время в примерах замерено на нашем компьютере (gcc 12 с -O2, Python 3.12), у вас цифры будут другими, а соотношения те же.

Считаем операции

Сумма массива из n чисел:

long long sum = 0;
for (int i = 0; i < n; i++)
    sum += a[i];

Тело цикла выполняется n раз. Вдвое больше чисел, вдвое больше работы. Такой рост называют линейным и пишут O(n).

Проверка, есть ли в массиве одинаковые числа, «в лоб»:

int has_dup_slow(const int *a, int n) {
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] == a[j])
                return 1;
    return 0;
}

Если повторов нет, сравниваются все пары: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Для n = 1000 это около полумиллиона сравнений, для n = 100 000 уже пять миллиардов. Рост квадратичный, O(n²).

Что значит O(...)

Запись O(g(n)) говорит, что при больших n число операций растёт не быстрее, чем g(n), умноженное на какую-то константу. Важна только скорость роста, а не точное число операций.

Войлочный кот Тиль стоит у подножия бумажной лестницы, где каждая ступенька вдвое выше предыдущей

Поэтому при оценке:

  • константы отбрасывают: 3n и n/2 это O(n);
  • младшие слагаемые отбрасывают: n²/2 + n/2 это O(n²), при больших n второе слагаемое ничего не решает;
  • основание логарифма не пишут: log₂ n и log₁₀ n отличаются в константу раз.

Чтобы почувствовать разницу между классами, посмотрите, сколько операций они дают:

Сложность n = 10 n = 1000 n = 10⁶ Пример
O(1) 1 1 1 элемент массива по индексу
O(log n) 3 10 20 бинарный поиск
O(n) 10 1000 10⁶ один проход по массиву
O(n log n) 33 10⁴ 2·10⁷ хорошая сортировка
O(n²) 100 10⁶ 10¹² все пары
O(2ⁿ) 1024 ≈10³⁰¹ все подмножества

На n = 10 всё мгновенно, поэтому на примере из условия медленное решение не отличить от быстрого. Разница видна только на больших тестах.

Замер того же поиска повторов: вариант O(n²) против сортировки с проверкой соседей, O(n log n).

n = 100000: O(n^2) 0, 1.764 s; O(n log n) 0, 0.0026 s
n = 200000: O(n^2) 0, 7.087 s; O(n log n) 0, 0.0054 s

Удвоили n, квадратичный вариант стал медленнее в 4 раза, а второй примерно в 2. На n = 200 000 разница больше чем в тысячу раз.

Правила для циклов

  • Циклы друг за другом складываются: O(n) + O(n²) = O(n²), остаётся самый тяжёлый.
  • Вложенные циклы перемножаются: внешний на n, внутренний на m, итого O(n·m).
  • Внутренний цикл от i до n всё равно даёт O(n²): в среднем он проходит половину, а половина это константа.
  • Цикл с постоянным числом шагов не меняет оценку: for (j = 0; j < 26; j++) внутри цикла по n даёт O(26n) = O(n).
  • Переменная делится или умножается на 2: for (i = n; i > 0; i /= 2) делает около log₂ n шагов, это O(log n).

Константы в O не видны, но на практике они важны. O(n) с телом из ста операций может работать дольше, чем O(n log n) с одной операцией, пока n небольшое.

Логарифм: бинарный поиск

В отсортированном массиве искомое число можно найти, каждый раз отбрасывая половину:

int binary_search(const int *a, int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x)
            return mid;
        if (a[mid] < x)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

После k шагов остаётся n / 2ᵏ элементов. Поиск кончается, когда остался один: n / 2ᵏ = 1, отсюда k = log₂ n. Для миллиона элементов это 20 шагов, ведь 2²⁰ = 1 048 576. Со счётчиком наш поиск в массиве из 10⁶ чисел сделал ровно 20 шагов и когда нашёл число, и когда его не было. Запись lo + (hi - lo) / 2 вместо (lo + hi) / 2 защищает от переполнения int при больших индексах.

Логарифм появляется везде, где задача на каждом шаге делится пополам: бинарный поиск, быстрое возведение в степень, сбалансированные деревья, а в сортировке слиянием log n уровней деления.

Скрытые циклы

Самые обидные O(n²) получаются, когда второй цикл не виден в коде.

strlen в условии цикла.

for (size_t i = 0; i < strlen(s); i++)
    if (s[i] == ' ')
        cnt++;

strlen сама проходит строку до конца, и вызывается она на каждой итерации. Строка из миллиона символов при сборке с -O0 обрабатывалась у нас 13,5 с, а с длиной, посчитанной один раз до цикла, 0,002 с. С -O2 gcc сам вынес strlen из цикла, но рассчитывать на это не стоит: посчитайте длину заранее.

in для списка в Python. Проверка x in data для списка просматривает его целиком, это O(n). 10 000 таких проверок по списку из 100 000 чисел заняли 5,17 с. Те же проверки по множеству set(data) в среднем O(1) и заняли 0,0002 с.

Ещё примеры: list.pop(0) и list.insert(0, x) сдвигают весь список, это O(n). Для очереди в Python есть collections.deque. Срез a[i:j] копирует элементы. Сложение строк s = s + c в цикле в C++ копирует строку каждый раз, лучше s += c.

Сложность сортировок

Сортировка Худший случай В среднем Память
пузырьком, вставками, выбором O(n²) O(n²) O(1)
слиянием O(n log n) O(n log n) O(n)
быстрая (quicksort) O(n²) O(n log n) O(log n) на стек в среднем
пирамидальная (heapsort) O(n log n) O(n log n) O(1)
подсчётом O(n + k) O(n + k) O(k), k это диапазон значений

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

В реальном коде пишите стандартную сортировку. std::sort в C++ начиная с C++11 обязан укладываться в O(n log n) сравнений в худшем случае (cppreference). В Python sorted() и list.sort() тоже работают за O(n log n).

Память тоже считают

Оценка памяти устроена так же. Сумма массива требует O(1) дополнительной памяти, сортировка слиянием O(n), таблица n × n занимает O(n²).

Перевести в байты просто: int занимает 4 байта, long long и double 8. Матрица int 10 000 × 10 000 это 10⁸ × 4 байта = 400 МБ, при лимите в 256 МБ она не поместится, даже если по времени всё хорошо. В Python числа занимают больше: список из миллиона целых у нас занял около 40 МБ против 4 МБ для массива int в C.

Рекурсия тоже расходует память: глубина n значит n кадров в стеке, то есть O(n) памяти, даже если в функции нет ни одного массива.

Уложится ли решение в лимит времени

Точное время заранее не узнать, но порядок прикинуть можно. Для оценки обычно берут, что C и C++ успевают порядка 10⁸ простых операций в секунду с запасом. Это ориентир с запасом, а не закон. Самый простой цикл сравнений из примера выше у нас делал около 3·10⁹ итераций в секунду, но в реальном решении есть операции тяжелее: деление, обращения к памяти вразброс, вызовы функций. В Python простой цикл for i in range(10**7): s += i у нас выполнился за 0,58 с, то есть около 2·10⁷ итераций в секунду. Встроенные функции вроде sum, sorted и in для set работают внутри интерпретатора на C и намного быстрее ручных циклов.

Отсюда ориентиры для лимита в 1 секунду на C++:

n до Подходит Пример
10–11 O(n!) перебор перестановок
20–25 O(2ⁿ) перебор подмножеств
500 O(n³) три вложенных цикла
5000 O(n²) все пары
10⁶ O(n log n) сортировка, бинарный поиск для каждого элемента
10⁸ O(n) один простой проход

Пример расчёта. В условии n ≤ 2·10⁵. Решение O(n²): (2·10⁵)² = 4·10¹⁰ операций, это сотни секунд даже на C. Решение O(n log n): 2·10⁵ × 18 ≈ 3,6·10⁶, это миллисекунды. Ограничения в условии часто подсказывают, какую сложность ждут: n ≤ 5000 намекает на O(n²), n ≤ 10⁵ и больше требует O(n log n) или O(n).

Как оценить свой код: порядок действий

  1. Найдите, от каких величин зависит работа: длина массива n, число запросов q, размер строки.
  2. Для каждого цикла определите, сколько раз он выполняется, и перемножьте вложенные.
  3. Проверьте вызовы внутри циклов: strlen, in для списка, pop(0), копирование строк и срезов, сортировку.
  4. Для рекурсии оцените число вызовов и глубину. Если вызов порождает два новых, как в наивном Фибоначчи, рост экспоненциальный.
  5. Подставьте максимальные значения из условия и сравните с ориентиром в 10⁸ операций в секунду.
  6. Если не уверены, замерьте: сгенерируйте тест максимального размера и запустите time ./prog < big.txt.

Как с этим помогает Tilpi

В чате задания Tilpi разбирает тему по шагам и объясняет код: можно показать своё решение и попросить оценить его сложность и найти место, где прячется лишний цикл. Если к заданию приложена лекция по алгоритмам, ответ опирается на неё и ссылается на страницу. Исполнитель запускает код в отдельной изолированной машине, пишет и прогоняет тесты, так что решение можно проверить на большом входе. Чат по своим файлам работает бесплатно с подтверждённой почтой в пределах лимитов, исполнитель на уровне «Быстрая» входит в тариф «Лайт», все уровни открыты с тарифа «Плюс».

ИИ для учёбы. По вашим лекциям.

Пришлите в чат лекцию, задачу или свой текст. Тилпи объяснит тему со ссылкой на страницу, разберёт решение по шагам и проверит оформление.

Оценить сложность решения в Tilpi