Big-O — шпаргалка с примерами

НЕ ОБЯЗАТЕЛЬНО ДЛЯ НОВИЧКОВ

Приветствую! Здесь вы наверняка найдете, что ищете. Примеры в лаборатории рассчитаны на то, что мы разбираем что-то конкретное.

Текущая статья посвящена o(1), O(log n), O(n), O(n²), примеры для ЕГЭ, олимпиад и собеседований, ловушки list и set..

Поэтому за теорией по текущей теме вам — в энциклопедию. Если ещё не погружались, то маршрут прост:

  1. Основы
  2. Система и сеть
  3. Данные и разметка
  4. Код и разработка
  5. Языки
  6. Искусственный интеллект
  7. Проект
  8. Инфраструктура и безопасность
  9. Спин-офф

Обязательно пройдитесь.

А теперь приступим к нашему предмету.

Теория и соседние материалы
Энциклопедия — разделы по вашей теме.

Навигация по примерам

Раздел Содержание
Что такое Big-O смысл без формул
Как оценить по коду циклы, вложенность, скрытые операции
Таблица классов от O(1) до O(n!)
Примеры с разбором код + таблицы + трассировка
Ловушки Python in, sort, pop(0)
До и после как убрать квадрат
Чек-лист n из условия → допустимая сложность

Что такое Big-O за 30 секунд

Big-O (нотация «О-большое») отвечает на один вопрос: если данных станет в 10 раз больше, во сколько раз примерно вырастет время работы?

  • O(1) — почти не вырастет (доступ по индексу a[5]).
  • O(n) — примерно в 10 раз (один проход по массиву).
  • O(n²) — примерно в 100 раз (два вложенных цикла по размеру данных).

В записи игнорируют константы: 3n + 100 и n оба называют O(n), потому что при большом n важен рост, а не «+100» или «×3».

Пример из жизни: найти имя в телефонной книге из 10 страниц можно листать подряд (O(n)). В книге из 10 000 страниц тот же приём станет мучением — нужен алфавитный указатель (O(log n) при бинарном поиске по отсортированному списку).

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

Три шага — хватает для большинства школьных и учебных задач.

Шаг 1. Найдите n

n — то, от чего растёт работа программы:

  • n = len(a) — длина массива;
  • n — число вершин графа, строк в файле, символов в строке;
  • иногда два параметра: n и m (таблица n × m).

Шаг 2. Посчитайте циклы и рекурсию

Увидели в коде Обычная оценка времени
Нет цикла по данным, фиксированные шаги O(1)
Один цикл for / while по n, тело простое O(n)
Два цикла по n друг внутри друга O(n²)
Три цикла по n O(n³)
На каждом шаге n делится пополам O(log n)
Сортировка встроенным sort() O(n log n)
Рекурсия с двумя ветками без памяти часто O(2ⁿ)

Шаг 3. Проверьте «скрытые» операции

Тело цикла O(1) только если внутри нет ещё одного прохода по n. Опасные места в Python:

  • x in my_list — линейный поиск O(n);
  • a.sort() — O(n log n);
  • a.pop(0) — сдвиг списка O(n).

Подробная таблица — в разделе ловушки Python.

Сложение и умножение:

  • Подряд O(n) + O(n) → O(n) (берётся худший, но тот же порядок).
  • Цикл O(n) с телом O(n) → O(n²) (умножаем).

Таблица классов

Класс Если n стало в 10 раз больше Где встречается
O(1) время почти то же a[i], dict[key], stack.pop()
O(log n) +несколько шагов бинарный поиск, деление пополам
O(n) ×10 сумма массива, линейный поиск, один Counter
O(n log n) ×10–×15 list.sort(), merge sort, heapsort
O(n²) ×100 пузырёк, все пары, in list в цикле
O(n³) ×1000 умножение матриц «в лоб»
O(2ⁿ) взрыв наивный Фибоначчи, полный перебор подмножеств
O(n!) ещё тяжелее все перестановки

Цепочка роста

При большом n (слева быстрее):

O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → … → O(2ⁿ) → O(n!)

Почему на олимпиаде важен порядок

При `n = 100 000` линейный алгоритм делает порядка 10⁵ шагов — обычно укладывается в лимит 1–2 секунды.

Квадратичный — порядка 10¹⁰ шагов — проверяющая система выдаст Time Limit Exceeded. Поэтому в условии смотрят на `n` и подбирают класс сложности до написания кода.

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

Дальше — полный разбор типовых фрагментов. Обозначение: n = len(a), если не сказано иное.

O(1) — константное время

Смысл: число операций ограничено сверху константой и не растёт вместе с n, когда вы уже держите массив в памяти и делаете одну операцию.

Пример 1 — первый и последний элемент

Задача: по списку вернуть первый и последний элемент.

def first_and_last(a: list[int]) -> tuple[int, int]:
    return a[0], a[-1]

if __name__ == "__main__":
    data = [10, 20, 30, 40]
    print(first_and_last(data))  # (10, 40)

Разбор:

Строка Смысл Сложность
a[0] обращение по индексу в списке Python O(1)
a[-1] последний элемент, индекс -1 O(1)
return (..) упаковка кортежа O(1)

Итого: O(1) на один вызов функции.

Пример 2 — стек

Задача: положить число на вершину стека и снять его.

def push_pop_stack(stack: list[int]) -> None:
    stack.append(42)   # добавление в конец
    top = stack.pop()  # снятие с конца
    print(top)

if __name__ == "__main__":
    s: list[int] = []
    push_pop_stack(s)
    print(s)  # []

Разбор:

Операция Почему O(1)
append пишет в конец массива, без сдвига всех элементов
pop() без индекса снимает с конца, тоже без сдвига «хвоста» с начала

На экзамене: стек для скобок, DFS с явным стеком — операции O(1) на шаг.

O(log n) — логарифм

Смысл: на каждом шаге объём работы уменьшается в фиксированное число раз (часто в 2). Удвоение n добавляет один лишний шаг, а не удваивает время.

Пример 1 — бинарный поиск

Задача: в отсортированном массиве найти индекс target или вернуть -1.

Пример трассировки (target = 8):

Шаг lo hi mid a[mid] Действие
1 0 4 2 6 6 < 8 → ищем правее, lo = 3
2 3 4 3 8 равно → ответ 3

Всего 2 итерации при n = 5. В худшем случае итераций порядка ⌈log₂ n⌉ + 1.

Разбор по строкам:

Строка Смысл
lo, hi границы текущего отрезка, где ещё может лежать ответ
mid = (lo + hi) // 2 середина; целочисленное деление
a[mid] == target нашли — выходим
a[mid] < target ответ только правее середины
hi = mid - 1 / lo = mid + 1 отбрасываем половину отрезка

Условие: массив должен быть отсортирован. Иначе «половины» не гарантируют, что элемент справа или слева.

Сложность: O(log n) по времени, O(1) дополнительной памяти.

Где искать в курсе: сортировка и поиск, 1122 §4.

Пример 2 — сколько раз поделить n пополам

def count_halving(n: int) -> int:
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

if __name__ == "__main__":
    for n in [8, 16, 1024]:
        print(n, "->", count_halving(n))

Вывод:

8 -> 3
16 -> 4
1024 -> 10

Смысл: 1024 = 2¹⁰ — нужно 10 делений, пока не станет 1. Это и есть интуиция log₂ n.

O(n) — линейное время

Смысл: каждый элемент входа обрабатывается константное число раз (часто ровно один).

Пример 1 — сумма массива

def sum_array(a: list[int]) -> int:
    total = 0
    for x in a:
        total += x
    return total

if __name__ == "__main__":
    print(sum_array([3, 1, 4, 1, 5]))  # 14

Разбор:

Строка Смысл
total = 0 накопитель суммы
for x in a ровно n итераций
total += x одно сложение за итерацию — O(1)

Сложность: O(n).

Пример 2 — линейный поиск

def linear_search(a: list[int], target: int) -> int:
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

Пример: a = [4, 2, 7, 1], target = 7 → индекс 2.

Сравнение с бинарным поиском:

Линейный Бинарный
Нужна сортировка? нет да
Время O(n) O(log n)
Когда выгоден мало данных, один проход много запросов, большой n

Пример 3 — частоты через Counter

from collections import Counter

def count_freq(a: list[int]) -> dict[int, int]:
    return Counter(a)

if __name__ == "__main__":
    print(count_freq([1, 2, 1, 3, 1]))
    # Counter({1: 3, 2: 1, 3: 1})

Смысл: Counter(a) один раз проходит по a и считает, сколько раз встретилось каждое значение.

Сложность: O(n) по времени, O(k) памяти, где k — число различных ключей (в худшем случае k = n).

O(n log n) — линейно-логарифмическое

Смысл: типичный результат «разбить задачу пополам log n раз и на каждом уровне сделать O(n) работы» — как в merge sort, или одна хорошая сортировка всего массива.

Пример 1 — sort и минимум с максимумом

def min_plus_max_after_sort(a: list[int]) -> int:
    a.sort()
    return a[0] + a[-1]

if __name__ == "__main__":
    data = [3, 1, 4, 1, 5]
    print(min_plus_max_after_sort(data))  # 1 + 5 = 6

Разбор:

Часть Сложность
a.sort() O(n log n) — Timsort в CPython
a[0] + a[-1] O(1)

Доминирует сортировка → O(n log n).

Замечание: минимум и максимум без сортировки можно за O(n) одним проходом. Сортировка здесь — учебный пример доминирования sort().

Пример 2 — merge sort (идея «уровней»)

Как считать O(n log n) без формул:

  1. Делим массив пополам, пока куски длины 1 — глубина рекурсии log n.
  2. На каждом уровне merge в сумме трогает все n элементов — O(n) на уровень.
  3. Уровней log n → O(n log n).

Разбор merge: указатели i и j только увеличиваются — каждый элемент left и right попадает в out один раз → слияние двух кусков длины n за O(n).

O(n²) — квадратичное время

Смысл: внешний цикл n раз, внутренний тоже порядка n → всего порядка n × n итераций.

Пример 1 — сортировка пузырьком

def bubble_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n):
        for j in range(0, n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

if __name__ == "__main__":
    arr = [3, 1, 4, 1, 5]
    bubble_sort(arr)
    print(arr)  # [1, 1, 3, 4, 5]

Разбор вложенных циклов:

Переменная Роль
i сколько элементов уже «всплыли» в конец
j сравниваем соседей a[j] и a[j+1]
n - 1 - i внутренний цикл короче — классический пузырёк

Число сравнений в худшем случае порядка n(n−1)/2 → O(n²).

Мини-трассировка для [3, 1, 2] (первые проходы):

Старт:     [3, 1, 2]
j=0: 3>1 → [1, 3, 2]
j=1: 3>2 → [1, 2, 3]   ← самый большой «всплыл»

На ЕГЭ пузырёк иногда пишут для наглядности; при n > 5000 на олимпиаде берут sort() — O(n log n).

Пример 2 — все пары с равными значениями

def count_equal_pairs(a: list[int]) -> int:
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                count += 1
    return count

if __name__ == "__main__":
    print(count_equal_pairs([1, 1, 2]))  # пары (0,1) → 1

Смысл: j начинается с i + 1, чтобы не считать пару дважды и не сравнивать элемент с самим собой.

Число итераций: для n элементов пар C(n,2) = n(n−1)/2 → O(n²).

Пример 3 — дубликат «в лоб»

def has_duplicate_naive(a: list[int]) -> bool:
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

Улучшение до O(n): один проход + set — см. раздел «До и после».

O(n³) — кубическое время

Задача: перемножить две квадратные матрицы n×n «в лоб» (как в школьной формуле).

Разбор тройного цикла:

Цикл Сколько раз
i n
j n
k n

Итого n³ обновлений C[i][j] → O(n³).

На практике: при n ≤ 200–500 в условии олимпиады куб часто ещё проходит; при n = 2000 уже нет.

O(2ⁿ) — экспоненциальное

Смысл: число веток растёт как степень двойки — классика наивной рекурсии без запоминания.

Наивный Фибоначчи

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

if __name__ == "__main__":
    print(fib_naive(10))  # 55 — ещё быстро
    # fib_naive(35) уже заметно тормозит

Дерево вызовов для fib_naive(5) (схема):

                    fib(5)
                   /      \
              fib(4)        fib(3)
             /     \        /     \
        fib(3) fib(2)  fib(2) fib(1)
        ..

Один и тот же fib(3) считается много раз — отсюда экспонента.

Разбор базы и шага:

Строка Смысл
if n <= 1 база рекурсии
два вызова fib(n-1) и fib(n-2) на каждом уровне удвоение веток без памяти

Сложность времени: O(2ⁿ) (точнее константа около φⁿ, но для Big-O пишут экспоненту).

Фибоначчи с мемоизацией — O(n)

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Смысл: перед пересчётом смотрим в memo — каждое k от 0 до n считается один раз.

Наивная рекурсия + memo
Время O(2ⁿ) O(n)
Память O(n) стек O(n) словарь + стек

Фибоначчи циклом — O(n) время, O(1) память

def fib_iter(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Разбор: цикл n итераций, две переменные — идеальный пример «та же задача, другой класс сложности».

O(n!) — факториал

Смысл: перебор всех перестановок — число вариантов n! (1×2×…×n).

Сколько перестановок (формула)

def permutations_count(n: int) -> int:
    fact = 1
    for k in range(2, n + 1):
        fact *= k
    return fact

if __name__ == "__main__":
    for n in range(1, 6):
        print(n, "->", permutations_count(n))

1 -> 1
2 -> 2
3 -> 6
4 -> 24
5 -> 120

Сам цикл умножения — O(n), но смысл факториала — когда ответов n! штук (полный перебор).

Печать всех перестановок (backtracking)

Вывод:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
..

Разбор:

Строка Смысл
len(path) == len(a) собрали полную перестановку — печатаем
for x in a пробуем поставить следующий элемент
if x in path элемент уже использован — пропуск (для списка без повторов)
path.pop() откат (backtracking) — пробуем другую ветку

Сложность: O(n!) листьев дерева перебора; плюс стоимость x in path — O(n) на шаг, если path список (для олимпиад лучше used: list[bool]).

Практический предел: полный перебор перестановок реалистичен при n ≤ 10–11.

Ловушки Python

Частая причина TLE на олимпиаде — «красивый» однострочник со скрытым O(n) внутри цикла по n.

Таблица операций

Выражение Сложность Замена
x in my_list O(n) x in my_set или ключ в dict
my_list.pop(0) O(n) collections.deque + popleft()
my_list.insert(0, x) O(n) deque.appendleft(x)
sorted(a) / a.sort() O(n log n) один раз до цикла запросов
a.count(x) в цикле по a O(n²) Counter(a) один раз
a + b (два списка) O(len(a)+len(b)) extend или накопление в одном списке

Ловушка 1 — in для списка в цикле

Задача: для каждого запроса q из queries проверить, есть ли q в data.

def bad_membership(queries: list[int], data: list[int]) -> list[bool]:
    return [q in data for q in queries]

def good_membership(queries: list[int], data: list[int]) -> list[bool]:
    seen = set(data)
    return [q in seen for q in queries]

if __name__ == "__main__":
    queries = [1, 99, 4]
    data = [1, 2, 3, 4, 5]
    print(bad_membership(queries, data))   # [True, False, True]
    print(good_membership(queries, data))  # то же

Разбор bad_membership:

Часть Сложность
цикл по queries длины q O(q)
q in data каждый раз O(n)
Итого O(q × n) → при q ≈ n это O(n²)

Разбор good_membership:

Часть Сложность
set(data) O(n) один раз
q in seen O(1) в среднем
Итого O(n + q)

Ловушка 2 — очередь на list

Почему pop(0) дорого: после удаления нулевого элемента Python сдвигает все остальные на одну позицию — O(n) на одну операцию. При n извлечениях получается O(n²).

popleft() у deque — O(1).

Подробнее про BFS и очереди — 1122 §9.

Пространственная сложность

Big-O для памяти считает дополнительную память (не считая сам вход, если иное не оговорено).

Пример Память Комментарий
Несколько переменных в цикле O(1)
b = a[:] O(n) копия списка
memo в Фибоначчи O(n) словарь
Таблица dp[n+1][m+1] O(n·m) классическое ДП
Рекурсия глубины log n O(log n) стек вызовов merge sort

Копия или разворот на месте

def reverse_extra_array(a: list[int]) -> list[int]:
    return a[::-1]

def reverse_in_place(a: list[int]) -> None:
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1
Функция Время Доп. память
reverse_extra_array O(n) O(n) новый список
reverse_in_place O(n) O(1)

Улучшение сложности — два варианта

Здесь два типовых сюжета: много проверок «есть в наборе?» и пара с суммой k.

Задача A — membership для списка запросов

Пример:

queries = [3, 99, 1]
data = [1, 2, 3, 4, 5]
# solve_fast -> ['yes', 'no', 'yes']
Версия Время Идея
solve_slow O(len(queries) × len(data)) линейный поиск в data на каждый запрос
solve_fast O(len(data) + len(queries)) хеш-множество для O(1) проверок

Задача B — two sum (есть ли пара с суммой k)

Разбор two_sum_fast по шагам (k = 9):

x k - x seen до шага Результат
2 7 {} 7 не в seen → кладём 2
7 2 {2} 2 в seen → пара найдена

Почему seen.add(x) после проверки: при k = 6, x = 3 пара (3, 3) допустима только если две тройки в массиве; одна тройка не должна матчиться сама с собой на той же позиции.

Полный разбор для ЕГЭ — 1122 §3.2.

Чек-лист перед экзаменом

  1. Выписать n из условия — длина массива, число вершин, строк.
  2. Посчитать вложенность циклов — перемножить размеры диапазонов.
  3. Проверить in, sort, pop(0) внутри циклов.
  4. Сопоставить с таблицей лимитов (ниже).
  5. Память — таблица n×m при n,m = 5000 уже десятки миллионов ячеек.
Ограничение n в условии Разумная сложность времени
≤ 20 O(2ⁿ), O(n!) с отсечением
≤ 500 O(n³)
≤ 5 000 O(n²)
≤ 10⁵ O(n log n)
≤ 10⁶ O(n) или O(n log n) с малой константой
Типичные формулировки в условии
  • «Гарантируется, что массив отсортирован» — можно бинарный поиск O(log n).
  • «Найдите любую пару» / «существует ли» — часто хватит set за O(n).
  • «Перестановки», «все варианты» — смотрите на n! и маленькое n.

Частые вопросы из поиска

Что значит O(n) простыми словами?

Время растёт примерно пропорционально размеру входа: данных в 10 раз больше — работы примерно в 10 раз больше. Пример — один цикл for x in a.

Чем O(n) отличается от O(n²)?

При O(n²) удвоение n увеличивает время примерно в 4 раза (произведение двух циклов по n). При O(n) — только в 2 раза. Два вложенных цикла по массиву — сигнал O(n²).

Почему сортировка — O(n log n)?

Хорошие сортировки (merge sort, Timsort в Python) многократно делят данные (log n уровней) и на каждом уровне объединяют за линейное время (n).

Нужно ли знать Big-O на ЕГЭ?

В явном виде редко спрашивают «запишите O(…)», но лимит времени и размер входа подразумевают правильный класс алгоритма. Шпаргалка по задачам — Алгоритмы на Python — ЕГЭ и олимпиадка.

Куда двигаться дальше

Цель Материал
Теория, структуры данных Нотация Большое O
Ω, Θ, платформы Анализ эффективности
Сортировки и поиск глава 2
Задачи с вводом-выводом Алгоритмы на Python — 1122
C++ в том же духе Олимпиадные шаблоны
Визуальная пауза Самопроверка