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

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

---

Для кого эта статья

Подборка готовых примеров на Python 3 с разбором «что делает каждая строка» и почему у алгоритма такая сложность. Материал подойдёт, если вы:

• готовитесь к ЕГЭ по информатике, олимпиадам или зачёту по алгоритмам;
• ищете в поиске «сложность алгоритма python», «big o notation примеры», «O(n) что значит»;
• пишете код и хотите понять, пройдёт ли решение по времени при n = 100 000;
• разбираете чужой код на ревью или собеседовании.

Каждый блок можно скопировать в файл complexity_demo.py и запустить: python complexity_demo.py. Теория без воды — в Нотация Большое O. Полные задачи с вводом-выводом — алгоритмы на Python — 1122.

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

Сначала прочитайте определение простыми словами и три шага оценки по коду. Затем откройте нужный класс — O(n), O(n²) и т.д. — и разберите пример построчно. В конце — ловушки Python и чек-лист по ограничению n.

---

Краткий указатель

Раздел	Содержание
Что такое 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.

def binary_search(a: list[int], target: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


if __name__ == "__main__":
    arr = [2, 4, 6, 8, 10]
    print(binary_search(arr, 8))   # 3
    print(binary_search(arr, 7))   # -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 (идея «уровней»)

def merge(left: list[int], right: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)


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

Как считать 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 «в лоб» (как в школьной формуле).

def matrix_multiply_naive(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C


if __name__ == "__main__":
    A = [[1, 2], [3, 4]]
    B = [[5, 6], [7, 8]]
    print(matrix_multiply_naive(A, B))
    # [[19, 22], [43, 50]]

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

Цикл	Сколько раз
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)

def print_permutations(a: list[int], path: list[int] | None = None) -> None:
    if path is None:
        path = []
    if len(path) == len(a):
        print(path)
        return
    for x in a:
        if x in path:
            continue
        path.append(x)
        print_permutations(a, path)
        path.pop()


if __name__ == "__main__":
    print_permutations([1, 2, 3])

Вывод:

[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

from collections import deque

def bad_queue(n: int) -> int:
    q = list(range(n))
    s = 0
    while q:
        s += q.pop(0)
    return s


def good_queue(n: int) -> int:
    q = deque(range(n))
    s = 0
    while q:
        s += q.popleft()
    return s

Почему 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 для списка запросов

def solve_slow(queries: list[int], data: list[int]) -> list[str]:
    out = []
    for q in queries:
        found = False
        for x in data:
            if x == q:
                found = True
                break
        out.append("yes" if found else "no")
    return out


def solve_fast(queries: list[int], data: list[int]) -> list[str]:
    index = set(data)
    return ["yes" if q in index else "no" for q in queries]

Пример:

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)

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


def two_sum_fast(a: list[int], k: int) -> bool:
    seen: set[int] = set()
    for x in a:
        if k - x in seen:
            return True
        seen.add(x)
    return False


if __name__ == "__main__":
    arr = [2, 7, 11, 15]
    print(two_sum_slow(arr, 9))   # True  (2+7)
    print(two_sum_fast(arr, 9))   # True

Разбор 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(…)», но лимит времени и размер входа подразумевают правильный класс алгоритма. Шпаргалка по задачам — 1122.

---

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

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

---