Big O
При сравнении алгоритмов нас интересует не конкретное время в миллисекундах, а то, как растёт количество работы при увеличении входных данных. Для этого используют специальную запись – Big O.
Эта запись позволяет коротко сказать, насколько быстро растёт объём работы алгоритма, когда размер входных данных n становится больше. Например:
O(1)O(log n)O(n)O(n²)Пока эти обозначения могут выглядеть непривычно. Но за каждым из них стоит довольно простая идея.
Допустим, у нас есть массив [ и алгоритм поиска:
function search(numbers, target): for number in numbers: if number == target: return true return falseВ худшем случае алгоритм проверит каждый элемент. Если элементов 10, проверок может быть около 10. Если элементов 1 000 – около 1 000. Если n = 1 000 000, проверок может быть около 1 000 000.
Количество работы растёт примерно вместе с n. Такой рост обозначают O(n). Запись читается как «О от n».
Big O не говорит, сколько именно миллисекунд займёт выполнение, а описывает характер роста количества работы.
При разборе алгоритма мы можем довольно подробно посчитать, сколько работы он выполняет. Например, один алгоритм проходит по массиву один раз – это примерно n операций. Другой проходит два раза:
function process(numbers): for number in numbers: ... for number in numbers: ...Это примерно 2n операций. Третий алгоритм выполняет примерно пять действий для каждого элемента – 5n. Такие записи полезны: они показывают, что алгоритмы действительно могут выполнять разное количество работы. Например, при n = 10:
| Примерный объём работы | Количество операций |
|---|---|
n | 10 |
2n | 20 |
5n | 50 |
100n | 1 000 |
Алгоритм с 100n операций явно делает намного больше работы, чем алгоритм с n. Теперь увеличим размер входных данных в десять раз – возьмём n = 100:
| Примерный объём работы | При n = 10 | При n = 100 |
|---|---|---|
n | 10 | 100 |
2n | 20 | 200 |
5n | 50 | 500 |
100n | 1 000 | 10 000 |
Конкретные значения остаются разными. Но во всех четырёх случаях при увеличении n в десять раз объём работы тоже увеличился примерно в десять раз. То есть у них один и тот же характер роста – линейный.
Поэтому удобно различать две вещи:
| Запись | Что показывает |
|---|---|
2n | Примерный объём работы |
O(n) | Характер его роста |
Например, два последовательных прохода по массиву дают:
Но при записи Big O постоянный множитель убирают:
То же самое:
Это не означает, что n, 5n и 100n выполняются одинаково быстро. Постоянный множитель может заметно влиять на реальное время работы.
Big O просто отвечает на другой вопрос: как будет расти объём работы, если размер входных данных продолжит увеличиваться?
Поэтому во время разбора алгоритма коэффициент можно сохранять, если он помогает понять количество работы:
А когда мы записываем итоговую оценку в Big O:
Есть одно важное исключение: убрать можно только постоянный множитель. Например:
Но если множитель сам зависит от входных данных, отбрасывать его нельзя. Например, есть два набора данных – n пользователей и m товаров, и для каждого пользователя нужно просмотреть все товары:
for user in users: for product in products: ...Работы примерно n * m. Множитель m – это размер второго набора данных: с другим списком товаров он будет другим, поэтому в записи он остаётся – O(nm). То же с таблицей из n строк и m столбцов: чтобы заполнить её, нужно примерно n * m действий. А если внутренний цикл проходит по тому же массиву, множитель равен n: n * n = n², то есть O(n²).
И аналогично запись 2n не имеет ничего общего с 2n: здесь n находится в степени, поэтому это уже совершенно другой тип роста – O(2n).
Начнём с самого простого случая. Есть массив [, и нам нужен элемент с индексом 3:
value = numbers[3]Неважно, сколько всего элементов в массиве – 10, 1 000 или 1 000 000: мы всё равно обращаемся к одному конкретному элементу. Количество работы почти не зависит от n. Такую сложность обозначают O(1).
Важно понимать: O(1) не означает «ровно одна операция». Например:
a = numbers[0]b = numbers[1]c = a + bЗдесь действий несколько. Но их количество остаётся постоянным независимо от размера массива. Поэтому это всё равно O(1).
Нужно найти значение в массиве:
function search(numbers, target): for number in numbers: if number == target: return true return falseВ худшем случае нужно проверить все n элементов. Если вход увеличится примерно в два раза, количество проверок тоже увеличится примерно в два раза. Это O(n).
Теперь рассмотрим вложенные циклы:
function printPairs(numbers): for i in numbers: for j in numbers: print(i, j)Для каждого элемента внешнего цикла внутренний цикл проходит по всем элементам ещё раз. Проследим это на массиве [:
printPairs для массива из 3 элементов.Если n = 3, получаем 3 * 3 = 9 итераций. Если n = 10 – уже 10 * 10 = 100. Если n = 1 000, то 1 000 * 1 000 = 1 000 000.
Это рост O(n²).
Есть алгоритмы, которые на каждом шаге уменьшают оставшуюся задачу сразу в несколько раз. Так работает поиск в отсортированном массиве, который каждый раз отбрасывает половину элементов.
Допустим, элементов 32. После первого шага остаётся примерно 16, затем 8, потом 4, затем 2 и наконец 1:
Получается 32 → 16 → 8 → 4 → 2 → 1: всего несколько шагов, хотя элементов было 32. Если элементов станет 1 024, понадобится около десяти таких делений пополам. Рост такого типа обозначают O(log n).
Размер входных данных может сильно увеличиться, а количество дополнительных шагов растёт очень медленно.
Сравним, сколько работы в худшем случае понадобится линейному алгоритму и алгоритму с делением пополам:
n | Линейный алгоритм | Деление пополам |
|---|---|---|
16 | 16 | 4 |
1 024 | 1 024 | 10 |
1 048 576 | 1 048 576 | 20 |
Когда элементов больше миллиона, линейному алгоритму может понадобиться больше миллиона проверок, а алгоритму с делением пополам – примерно 20 шагов. Именно поэтому алгоритмы с таким ростом могут очень хорошо работать на больших данных.
На картинке – четыре типа роста на общих осях: по горизонтали размер входных данных n, по вертикали количество работы. Какой цвет какому типу принадлежит, показывает легенда, а цветные зоны между линиями отделяют один тип роста от другого.
nПри n = 10 линии ещё близко друг к другу: O(1) держится на единице, O(log n) доходит примерно до 3, O(n) – до 10, а O(n²) – до 100.
При n = 1 000 разница уже огромная: O(1) так и стоит на единице, O(log n) едва доходит до 10, O(n) – до 1 000, а O(n²) – до миллиона. Это и есть разный характер роста: чем круче линия уходит вверх с ростом n, тем быстрее растёт количество работы.
Представим два алгоритма. Первый выполняет примерно 100n операций, второй – n². Для очень маленького n первый алгоритм может оказаться медленнее. Например, при n = 10 получаем:
Несмотря на то что первый алгоритм имеет O(n), а второй – O(n²), на этом конкретном размере второй может выполнить меньше действий. Но при росте n ситуация изменится. Если n = 10 000, то:
Big O особенно полезна, когда нас интересует поведение алгоритма на больших входных данных. Это описание масштабирования, а не точного времени выполнения.
На первых этапах можно использовать несколько простых ориентиров. Если количество действий не зависит от n, это обычно O(1):
value = numbers[0]Если один цикл проходит по всем элементам – обычно O(n):
for number in numbers: ...Если есть два вложенных прохода по тем же n элементам – обычно O(n²):
for i in numbers: for j in numbers: ...Если на каждом шаге задача уменьшается примерно вдвое, получается O(log n):
while n > 1: n = n // 2Это только ориентиры: в реальных алгоритмах код бывает сложнее.
Здесь легко ошибиться. Посмотрим на два последовательных цикла:
for number in numbers: ...for number in numbers: ...Первый делает около n итераций. Второй тоже около n. Получается n + n = 2n, после упрощения – O(n). Теперь сравним с вложенными циклами:
for i in numbers: for j in numbers: ...Внутренний цикл выполняется целиком для каждой итерации внешнего. Получаем n * n = n², то есть O(n²).
Мы уже убирали постоянный множитель. Есть и второе правило упрощения: если объём работы складывается из нескольких частей с разным характером роста, в Big O оставляют ту, что растёт быстрее всех. Например, есть вложенный цикл, а после него ещё один обычный проход:
function process(numbers): for i in numbers: for j in numbers: ... for number in numbers: ...Первая часть выполняет примерно n * n операций, вторая – n. Итого n² + n. При n = 10 это 100 против 10, а при n = 1 000 – уже 1 000 000 против 1 000: квадратная часть полностью доминирует.
Поэтому O(n² + n) упрощают до O(n²): остаётся часть, которая растёт быстрее остальных.
Оба правила работают вместе. Например, 3n² + 2n + 100 – это O(n²): множители 3 и 2 убираем, из трёх слагаемых оставляем самое быстрорастущее.
Возьмём обычный поиск:
function search(numbers, target): for number in numbers: if number == target: return true return falseЕсли искомый элемент находится первым, потребуется всего одна проверка. Но если он находится последним или вообще отсутствует, придётся пройти весь массив. Поэтому:
| Случай | Сложность |
|---|---|
| Лучший случай | O(1) |
| Худший случай | O(n) |
Один и тот же алгоритм можно отдельно анализировать в лучшем, среднем и худшем случаях. На практике чаще всего смотрят именно на худший случай – так проще понять пределы алгоритма и оценить, сколько работы ему может понадобиться в самой неудачной ситуации.
Полезно не воспринимать обозначения как оценки качества. Например, O(n²) не означает, что алгоритм автоматически плохой. Если n = 20, такой алгоритм может прекрасно подходить для задачи. И наоборот, сложный алгоритм с лучшей теоретической сложностью иногда не имеет смысла на маленьких данных.
Big O – это инструмент, который позволяет понять, как будет изменяться стоимость решения при росте входных данных. А уже после этого можно решать, подходит ли алгоритм для конкретной задачи.
// теперь вы знаете
- Big O описывает, как растёт количество работы при увеличении
n, а не время в секундах - Постоянные множители отбрасывают:
2n– этоO(n); из суммы оставляют самое быстрорастущее:n² + n– этоO(n²) O(1)– работа не зависит отn,O(log n)– задача каждый шаг уменьшается вдвое,O(n)– один проход по всем элементам,O(n²)– вложенные проходы- Последовательные циклы складывают работу, вложенные – умножают
- Лучший и худший случаи различаются: у поиска это
O(1)иO(n); обычно смотрят на худший - Меньшая Big O не значит «быстрее на любых данных»: при малых
nалгоритм с100nможет проигратьn²
Что в первую очередь описывает Big O?
Алгоритм выполняет примерно 5n операций. Какую сложность обычно записывают?
Количество операций можно примерно записать как n² + 3n + 10. Какую сложность запишет Big O?
Сложность алгоритма – O(n). Если n примерно удвоится, как обычно изменится объём работы?
Сложность алгоритма – O(n²). Во сколько раз примерно возрастёт основная часть работы, если n увеличится в два раза? Введите число.
Есть 1 024 элемента. Алгоритм на каждом шаге уменьшает оставшееся количество элементов примерно вдвое. Какое количество шагов ближе всего к ожидаемому?
Алгоритм A имеет сложность O(n), а алгоритм B – O(n²). Можно ли только по этим обозначениям утверждать, что A будет быстрее B на любых входных данных?
Какова сложность следующего фрагмента?
for value in numbers:print(value)for value in numbers:print(value)
Выберите все правильные утверждения.
Выбери все верные варианты