Как анализировать сложность кода

Увидеть готовое обозначение O(n²) гораздо проще, чем самому посмотреть на код и понять, откуда оно взялось. На практике никто не подписывает функцию так:

# O(n²)function process(numbers):    ...

Обычно перед нами просто код, и наша задача – определить, как будет расти количество работы и дополнительной памяти при увеличении входных данных. Для этого не нужно считать каждую инструкцию: достаточно научиться замечать несколько повторяющихся закономерностей.

Сначала определяем размер входа

Перед анализом нужно понять, что именно будет расти. Рассмотрим функцию:

containsпсевдокод

1function contains(numbers, target):2    for number in numbers:3        if number == target:4            return true56    return false

Здесь размер задачи определяется количеством элементов в numbers, поэтому обозначим его n = numbers.length. Если элементов становится больше, цикл потенциально выполняет больше итераций – именно n и будет использоваться при оценке сложности.

Но n не всегда означает размер массива. Если алгоритм работает со строкой, n может означать количество символов (text.length), если с вершинами графа – количество вершин, если с файлами – количество файлов. n – это просто обозначение величины входа, от которой зависит объём работы.

Код без повторений обычно даёт O(1)

Начнём с простого примера:

firstTwoSumпсевдокод

1function firstTwoSum(numbers):2    first = numbers[0]3    second = numbers[1]45    return first + second

Здесь выполняется фиксированное количество действий. Неважно, в массиве 10 элементов или 1 000 000 – функция всё равно работает только с двумя из них. Поэтому время O(1).

То же самое относится к большему количеству обычных инструкций: если взять три элемента и сложить их, действий станет больше, но их количество всё равно не зависит от n. Важно смотреть не на количество строк кода, а на то, растёт ли число выполняемых действий вместе с входными данными.

Один полный проход обычно даёт O(n)

Теперь добавим цикл:

printAllпсевдокод

1function printAll(numbers):2    for number in numbers:3        print(number)

Если n = 5, тело цикла выполнится примерно 5 раз. Если n = 1 000 – примерно 1 000. Количество работы растёт вместе с n, поэтому это O(n) – один из самых распространённых случаев.

Последовательные участки складываются

Рассмотрим код:

processпсевдокод

1function process(numbers):2    for number in numbers:3        print(number)45    for number in numbers:6        print(number)

Первый цикл – n итераций, второй тоже n. Итого n + n = 2n, а постоянный множитель для Big O не важен: получается O(n).

Теперь добавим к циклу обычные инструкции – например, взять первый элемент до цикла и последний после него. Условно получаем 1 + n + 1, то есть n + 2. При больших n главную роль играет n, поэтому снова O(n).

Правило простое: последовательные участки работы складываются, а затем в Big O остаётся самая быстрорастущая часть.

Вложенные циклы обычно перемножаются

Теперь сравним два случая. Циклы могут идти друг за другом:

process – подрядпсевдокод

1function process(numbers):2    for number in numbers:3        print(number)45    for number in numbers:6        print(number)

А могут находиться один внутри другого:

process – вложеннопсевдокод

1function process(numbers):2    for first in numbers:3        for second in numbers:4            print(first, second)

В первом случае работа складывается: n + n, то есть O(n). Во втором внутренний цикл выполняется целиком для каждой итерации внешнего: n * n, то есть O(n²).

Эта разница встречается настолько часто, что её стоит научиться замечать сразу. Пошаговый разбор вложенных циклов есть в уроке Big O.

Цикл не всегда означает O(n)

Важно смотреть не просто на наличие цикла, а на то, как изменяется его состояние. Например:

reduceпсевдокод

1function reduce(n):2    while n > 1:3        n = n // 2

Здесь значение уменьшается не на единицу, а сразу в два раза. Если начать с 32, получим 32 → 16 → 8 → 4 → 2 → 1 – всего несколько итераций. Такой рост – O(log n).

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

Сколько итераций делает каждый цикл?

Вложенный цикл – за один вход в него.

function process(numbers):

for number in numbers:итераций

print(number)

k = numbers.length

while k > 1:итераций

k = k // 2

for first in numbers:итераций

for second in numbers:итераций

print(first, second)

Почему

Первый цикл проходит все n элементов. while каждый раз делит k пополам – это log n итераций. Внешний цикл по numbers делает n итераций, и на каждой из них внутренний тоже делает n: вместе n * n.

строка 2 – n
строка 6 – log n
строка 9 – n
строка 10 – n

Условия сами по себе обычно не увеличивают сложность

Если ветки не содержат циклов, выполнится только одна из них, и количество работы не зависит от размера входа – это O(1). Теперь поставим условие внутри цикла:

countPositiveпсевдокод

1function countPositive(numbers):2    count = 034    for number in numbers:5        if number > 0:6            count += 178    return count

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

Если ветки разные – смотрим на более дорогую

Представим функцию, у которой ветки делают разный объём работы:

processпсевдокод

1function process(numbers, detailed):2    if detailed:3        for first in numbers:4            for second in numbers:5                print(first, second)6    else:7        for number in numbers:8            print(number)

При detailed == false работа примерно O(n), при detailed == true – O(n²). Если мы хотим оценить верхнюю границу работы функции, нас интересует более дорогой вариант – O(n²). Это тот же принцип, что и при разговоре о худшем случае.

Не все вложенные циклы делают ровно n² операций

Посмотрим на вложенный цикл, который начинается не с начала массива, а сразу после текущего элемента:

Пары без повторов – по шагам

n = numbers.length

В массиве [4, 7, 2, 9] четыре элемента: n = 4. Пар пока нет.

pairs = 0

for i = 0; i < n; i += 1:

for j = i + 1; j < n; j += 1:

pairs += 1

В массиве [4, 7, 2, 9] четыре элемента: n = 4. Пар пока нет.

Внешний цикл начинает с первого элемента: i = 0.

Пара (4, 7) – это 1-я по счёту.

Пара (4, 2) – это 2-я по счёту.

Пара (4, 9) – это 3-я по счёту.

Внешний цикл переходит дальше: i = 1. Внутренний пойдёт только по элементам правее.

Пара (7, 2) – это 4-я по счёту.

Пара (7, 9) – это 5-я по счёту.

Внешний цикл переходит дальше: i = 2. Внутренний пойдёт только по элементам правее.

Пара (2, 9) – это 6-я по счёту.

Последний элемент: правее него ничего нет, поэтому внутренний цикл не делает ни одного круга.

Готово: пар получилось 6, а n * n – это 16. Работы меньше, но при росте n она всё равно растёт примерно как квадрат – это O(n²).

Пар0

Внутренний цикл здесь не всегда проходит n элементов: сначала почти n раз, затем чуть меньше, потом ещё меньше. Для пяти элементов количество пар будет 4 + 3 + 2 + 1, то есть меньше, чем 5 * 5.

Но если увеличить n, количество пар всё равно растёт примерно как квадрат n, поэтому сложность остаётся O(n²). Big O не требует, чтобы алгоритм выполнял ровно n² действий – нас интересует тип роста.

Разные входы лучше обозначать разными буквами

Представим функцию, которая работает сразу с двумя массивами:

compareпсевдокод

1function compare(first, second):2    for a in first:3        for b in second:4            print(a, b)

Допустим, first.length = n, а second.length = m. Внешний цикл выполняется n раз, внутренний – m раз для каждой итерации внешнего. Получаем n * m, то есть O(nm).

Не стоит автоматически писать O(n²): размеры двух массивов могут быть совершенно разными. Если в первом 10 элементов, а во втором 1 000 000, одна буква n скрыла бы важную информацию. Поэтому независимые размеры входных данных обычно обозначают разными переменными.

Сложность функции может состоять из нескольких частей

Посмотрим на пример, где один участок идёт за другим:

processпсевдокод

1function process(numbers):2    for number in numbers:3        print(number)45    for first in numbers:6        for second in numbers:7            print(first, second)

Первый участок – O(n), второй – O(n²), вместе O(n + n²). Но при увеличении n квадратная часть растёт намного быстрее, поэтому итоговая сложность O(n²).

Порядок такой: оценить отдельные части, объединить их и оставить доминирующий рост. Это гораздо надёжнее, чем пытаться угадать ответ, просто взглянув на количество циклов.

Тот же подход работает и для памяти

Рассмотрим функцию, которая создаёт новый массив:

processпсевдокод

1function process(numbers):2    result = []34    for number in numbers:5        result.push(number * 2)67    return result

По времени это один проход – O(n). По памяти создаётся новый массив размером около n – тоже O(n). А у поиска максимума проход такой же, но дополнительная память остаётся постоянной: время O(n), память O(1).

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

Пошаговый способ анализа

Чтобы не определять сложность на глаз, можно использовать один и тот же порядок действий:

После этого так же отдельно оценивается дополнительная память

Разберём полный пример

Посмотрим на функцию, которая проверяет, есть ли в массиве повторяющиеся значения:

Сначала определяем размер входа: n = numbers.length. Затем смотрим на работу – есть внешний цикл, внутри него ещё один цикл по части массива. Количество сравнений растёт примерно как количество возможных пар элементов, поэтому время O(n²).

Какие дополнительные данные создаёт алгоритм? Только несколько переменных – i и j. Их количество не растёт вместе с n, поэтому память O(1).

Характеристика	Оценка	Почему
Время	`O(n²)`	Сравнений примерно столько, сколько пар элементов
Память	`O(1)`	Только `i` и `j` – их число не зависит от `n`

Ту же задачу можно решить и иначе – используя дополнительную память, но сократив время работы. Анализ сложности как раз и позволяет сравнивать несколько решений одной задачи.

Не нужно угадывать Big O по внешнему виду

На первых этапах очень хочется использовать простые правила: «один цикл – O(n)», «два цикла – O(n²)», «нет циклов – O(1)». Иногда они дают правильный ответ, но не всегда.

Например, у цикла while n > 1: n = n // 2 сложность O(log n), хотя цикл всего один. А два прохода по разным массивам:

for value in first:    ...for value in second:    ...

при входах размера n и m дают O(n + m), а не O(n).

Поэтому надёжнее задавать вопрос: сколько раз эта часть кода выполнится при увеличении входа? Тогда Big O становится не набором правил для запоминания, а способом описать реальное поведение программы.

// теперь вы знаете

Анализ начинается с размера входа: n – это то, что растёт (элементы массива, символы строки, вершины графа)
Количество строк кода не определяет сложность: важно, растёт ли число действий вместе с n
Один полный проход по входу – обычно O(n)
Последовательные участки складываются: n + n = 2n, а после упрощения – O(n)
Вложенные проходы перемножаются: n * n, то есть O(n²)
Цикл не гарантирует O(n): если задача на каждом шаге уменьшается вдвое, это O(log n)
if сам по себе не повышает сложность, а у разных веток берут более дорогую
Внутренний цикл от i + 1 даёт меньше работы, чем n * n, но рост остаётся квадратичным
Независимые входы обозначают разными буквами: n и m дают O(nm) или O(n + m)
Время и дополнительная память оцениваются отдельно: у одной и той же функции может быть O(n) и O(1)

Проверьте себя

Какова временная сложность этой функции?

function first(numbers):
    return numbers[0]

O(1)

O(log n)

O(n)

O(n²)

Сопоставьте код и его временную сложность.

# A
value = numbers[5]
# B
for value in numbers:
    print(value)
# C
for first in numbers:
    for second in numbers:
        print(first, second)
# D
while n > 1:
    n = n // 2

Фрагмент A

Фрагмент B

Фрагмент C

Фрагмент D

Какова временная сложность этого кода?

function process(numbers):
    for number in numbers:
        print(number)
    for number in numbers:
        print(number)

O(1)

O(n)

O(2n)

O(n²)

Массив numbers = [1, 2, 3]. Чему равно count к концу каждого круга внешнего цикла?

function countPairs(numbers):

count = 0

for first in numbers:

for second in numbers:

count += 1

return count

	Шаг	`count`
	first = 1
	first = 2
	first = 3

Правильная таблица

Шаг	count
first = 1	3
first = 2	6
first = 3	9

На каждом круге внешнего цикла внутренний делает три итерации. Всего 3 * 3 = 9 – это квадратный рост.

Какова временная сложность этой функции?

function reduce(n):
    while n > 1:
        n = n // 2

O(1)

O(log n)

O(n)

O(n²)

Распределите фрагменты по временной сложности. Все циклы идут по массиву из n элементов.

Элементы

O(1)

O(n)

O(n²)

Решение и разбор

O(1): result = numbers[0] + numbers[1], first = numbers[0] и last = numbers[numbers.length - 1]O(n): Один цикл for value in numbers с печатью значенияO(n²): Цикл по массиву, а внутри него ещё один цикл по тому же массиву

Почему

Обращения по индексу не зависят от размера массива. Один проход даёт O(n), проход внутри прохода – n * n.

Есть два массива: first.length = n, second.length = m. Какова временная сложность этого кода?

for a in first:
    for b in second:
        print(a, b)

O(n)

O(n²)

O(n + m)

O(nm)

У функции два вложенных цикла. Можно ли только по этому факту утверждать, что её сложность O(n²)?

Как упростить O(n² + n + 10)?

O(10)

O(n)

O(n²)

Оставить O(n² + n + 10)

Выберите все правильные утверждения.

Выбери все верные варианты

Один цикл всегда означает O(n).

Два последовательных прохода по одному массиву обычно дают O(n).

Два вложенных полных прохода по n элементам обычно дают O(n²).

Количество строк кода точно определяет сложность.

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

Если входы независимы, их размеры обозначают разными переменными.

Каковы время и дополнительная память этой функции?

function copy(numbers):
    result = []
    for number in numbers:
        result.push(number)
    return result

Время O(1), память O(n)

Время O(n), память O(1)

Время O(n), память O(n)

Время O(n²), память O(n)

Предыдущий урокПространственная сложность Это конец курсаАлгоритмы и структуры данных – оглавление