Математика для O-нотации: логарифмы, степени и скорость роста

← назад к разделу

Чтобы сравнивать алгоритмы, во всём разделе используется O-нотация: O(1), O(N), O(log N), O(N²). Под этими значками прячется совсем немного школьной математики — степени, логарифмы и понятие «как быстро растёт функция». Многие успели её подзабыть: логарифмы проходят в школе, а потом годами не встречают. Эта статья — короткая вспоминалка с нуля, чтобы дальше log N и N² читались без запинки. Ничего сложного: только то, что реально нужно, чтобы понимать скорость алгоритмов.

Степени: N в квадрате и двойка в степени N

Степень — это короткая запись умножения числа самого на себя. N² («N в квадрате») — это N × N, N³ — это N × N × N, а N в степени k — это N, умноженное само на себя k раз.

N²  = N × N        для N = 10  →  100
N³  = N × N × N    для N = 10  →  1000
2ⁿ  = 2 × 2 × … (N раз)   для N = 10  →  1024

Разница между N² и 2ⁿ — принципиальная, хоть на N = 10 числа и близки (100 против 1024).

• В N² растёт основание, а показатель степени фиксирован (двойка). Удвоили данные — работы стало вчетверо больше. Это квадратичный рост — быстрый, но предсказуемый.
• В 2ⁿ фиксировано основание (двойка), а растёт показатель — само N. Каждый лишний элемент удваивает результат. Это экспоненциальный рост, он взрывается: при N = 30 это уже больше миллиарда, при N = 60 — больше, чем секунд от Большого взрыва.

Логарифмы: обратная сторона степени

Логарифм — это ответ на обратный вопрос. Степень спрашивает: «сколько будет 2 в степени 3?» (ответ 8). Логарифм спрашивает наоборот: «в какую степень возвести 2, чтобы получить 8?» (ответ 3). Записывают это так: log₂ 8 = 3.

Для алгоритмов удобнее другое, совершенно наглядное определение того же самого:

log₂ N — это сколько раз число N нужно поделить пополам, чтобы дойти до 1.

Отсюда два вывода, которые и делают логарифм таким важным для алгоритмов:

• Логарифм растёт очень медленно. Данные выросли в тысячу раз — а число делений пополам увеличилось всего на 10 (log₂ 1000 ≈ 10, потому что 2¹⁰ = 1024). Для миллиона log₂ 1 000 000 ≈ 20, для миллиарда — всего 30. Поэтому алгоритм на log N почти не замечает роста данных.
• Основание логарифма для O-нотации неважно. log₂ N и log₁₀ N отличаются лишь постоянным множителем, а константы в O-нотации отбрасывают. Поэтому пишут просто O(log N), не уточняя основание.

Прикинуть log₂ N в уме легко: это число двоичных разрядов минус один, или просто «сколько раз влезает удвоение». Ориентиры стоит запомнить: log₂ 1000 ≈ 10, log₂ 1 000 000 ≈ 20, log₂ 1 000 000 000 ≈ 30.

Как быстро растут разные функции

Вся суть O-нотации — в том, как функция ведёт себя, когда N становится большим. Вот главные «скорости роста» от самой медленной к самой быстрой и их значения на N = 10, 100 и 1000:

Разрыв между строчками — это разница между «мгновенно» и «не дождёшься». На тысяче элементов логарифм — это 10 шагов, а квадрат — миллион; на миллионе разрыв уже в сто тысяч раз.

Как из этого читается O-нотация

O-нотация берёт формулу числа операций и оставляет от неё только самое главное — как она растёт на больших N. Правил всего два:

1. Отбрасываем константы и множители. 3N и 100N — это всё равно O(N): вдвое больше данных — вдвое больше работы, коэффициент неважен.
2. Оставляем самое быстрорастущее слагаемое. В сумме N² + N + 100 при большом N всё решает N²: на N = 1000 это 1 000 000 + 1000 + 100 — вклад младших слагаемых теряется. Значит O(N²).

5N + 3        → O(N)
N² + 10N + 7  → O(N²)      (N² перевешивает)
2·N·log N     → O(N·log N)
константа 42  → O(1)

Почему так грубо? Потому что O-нотация отвечает не на вопрос «сколько миллисекунд», а на вопрос «что будет, когда данных станет очень много». На маленьких N любой алгоритм быстрый; разница проявляется на больших, и там правит самое быстрорастущее слагаемое. Как именно эту мерку применяют к массивам и поиску — в следующей статье: Массивы, двоичный поиск и O-нотация.

Коротко

• Степень N² — это N×N (квадратичный рост, удвоение данных → вчетверо работы). 2ⁿ — двойка, умноженная сама на себя N раз (экспонента, взрывной рост).
• Логарифм log₂ N — сколько раз поделить N пополам до 1. Растёт очень медленно: миллион — это ~20, миллиард — ~30. Основание для O-нотации неважно.
• Скорости роста по возрастанию: 1 < log N < N < N·log N < N² < 2ⁿ. Разрыв между ними на больших N — колоссальный.
• O-нотацию читают так: отбрось константы и множители, оставь самое быстрорастущее слагаемое. 3N² + 5N + 9 → O(N²).

Что почитать дальше

• Массивы, двоичный поиск и O-нотация — где эта математика впервые работает: почему двоичный поиск это O(log N).
• Рекурсия — «разделяй и властвуй», откуда берётся N·log N в быстрых сортировках.
• Нетривиальная сортировка — как алгоритмы уходят от O(N²) к O(N·log N).