Математика для 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² и 2ⁿ — принципиальная, хоть на N = 10 числа и близки (100 против 1024). Проще всего увидеть её, посчитав обе величины на растущем N:

public class Growth {
    public static void main(String[] args) {
        for (int n = 10; n <= 30; n += 10) {
            System.out.println("N=" + n + "  N в квадрате = " + (long) n * n + "  2 в степени N = " + (1L << n));
        }
    }
}

package main

import "fmt"

func main() {
	for n := 10; n <= 30; n += 10 {
		fmt.Printf("N=%d  N в квадрате = %d  2 в степени N = %d\n", n, n*n, 1<<n)
	}
}

for (let n = 10; n <= 30; n += 10) {
  console.log(`N=${n}  N в квадрате = ${n * n}  2 в степени N = ${2 ** n}`);
}

for n in range(10, 31, 10):
    print(f"N={n}  N в квадрате = {n * n}  2 в степени N = {2 ** n}")

Квадрат на N = 30 — это 900, всё ещё мелочь. Двойка в степени 30 — уже миллиард.

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

Откуда экспонента берётся в задачах, если никто не возводит двойку в степень N явно: из перебора вариантов. У набора из N вещей ровно 2ⁿ подмножеств, потому что каждую вещь либо берут, либо нет, и это два независимых выбора на каждую. Перебрать все наборы товаров на сумму, все комбинации флагов, все способы выбрать команду это 2ⁿ шагов; перебрать все порядки, в которых можно объехать N городов, это N!, что растёт ещё быстрее (для двадцати городов два с половиной квинтиллиона). Когда в задаче звучит «все возможные наборы» или «все расстановки», ищите либо маленькое N, либо приём, который перебор сокращает: отсечение, динамическое программирование, жадный выбор; они дальше в разделе.

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

Логарифм — это ответ на обратный вопрос. Степень спрашивает: «сколько будет 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), не уточняя основание.

Проверить это можно прямым счётом: делим число пополам, пока не дойдём до единицы, и считаем шаги.

public class Halvings {
    public static void main(String[] args) {
        for (long n : new long[]{16, 1024, 1_048_576}) {
            long value = n;
            int steps = 0;
            while (value > 1) {
                value /= 2;
                steps++;
            }
            System.out.println(n + ": делений пополам = " + steps);
        }
    }
}

package main

import "fmt"

func main() {
	for _, n := range []int{16, 1024, 1_048_576} {
		value, steps := n, 0
		for value > 1 {
			value /= 2
			steps++
		}
		fmt.Printf("%d: делений пополам = %d\n", n, steps)
	}
}

for (const n of [16, 1024, 1_048_576]) {
  let value = n;
  let steps = 0;
  while (value > 1) {
    value = Math.floor(value / 2);
    steps++;
  }
  console.log(`${n}: делений пополам = ${steps}`);
}

for n in (16, 1024, 1_048_576):
    value, steps = n, 0
    while value > 1:
        value //= 2
        steps += 1
    print(f"{n}: делений пополам = {steps}")

Миллион с небольшим — двадцать шагов. Прикинуть log₂ N в уме тоже легко: это число двоичных разрядов минус один, то есть логарифм, округлённый вниз. Ориентиры стоит запомнить: log₂ 1000 ≈ 10, log₂ 1 000 000 ≈ 20, log₂ 1 000 000 000 ≈ 30.

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

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

«≈3, ≈7, ≈10» в строке логарифма это log₂ 10 ≈ 3,3, log₂ 100 ≈ 6,6 и log₂ 1000 ≈ 10: данные выросли в сто раз, а шагов прибавилось семь.

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

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

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

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

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

Потренируемся: назвать порядок роста по коду

Главный навык этой статьи не считать логарифмы, а посмотреть на цикл и сказать, как он растёт. Четыре кусочка, попробуйте назвать O для каждого до того, как читать ответ ниже.

for (int i = 0; i < n; i++) sum += a[i];                         // 1

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) if (a[i] == a[j]) pairs++;   // 2

for (int size = n; size > 1; size /= 2) steps++;                 // 3

for (int i = 0; i < n; i++)
    for (int size = n; size > 1; size /= 2) work++;              // 4

for i := 0; i < n; i++ { sum += a[i] }                            // 1

for i := 0; i < n; i++ {
	for j := i + 1; j < n; j++ { if a[i] == a[j] { pairs++ } }    // 2
}

for size := n; size > 1; size /= 2 { steps++ }                    // 3

for i := 0; i < n; i++ {
	for size := n; size > 1; size /= 2 { work++ }                 // 4
}

for (let i = 0; i < n; i++) sum += a[i];                              // 1

for (let i = 0; i < n; i++)
  for (let j = i + 1; j < n; j++) if (a[i] === a[j]) pairs++;         // 2

for (let size = n; size > 1; size = Math.floor(size / 2)) steps++;    // 3

for (let i = 0; i < n; i++)
  for (let size = n; size > 1; size = Math.floor(size / 2)) work++;   // 4

for i in range(n): total += a[i]                     # 1

for i in range(n):
    for j in range(i + 1, n):
        if a[i] == a[j]: pairs += 1                  # 2

size = n
while size > 1: size //= 2; steps += 1               # 3

for i in range(n):
    size = n
    while size > 1: size //= 2; work += 1            # 4

Первый цикл делает ровно N шагов, это O(N). Второй перебирает пары: для i = 0 внутренний цикл делает N−1 шагов, для следующего N−2, и так до нуля; сумма N·(N−1)/2, старшее слагаемое N², значит O(N²): половина и минус N отброшены по двум правилам выше. Третий делит размер пополам, пока не дойдёт до единицы, это и есть log₂ N шагов, O(log N). Четвёртый вкладывает третий в первый: N раз по log N, O(N·log N). Общий приём: считать, сколько раз выполнится самая внутренняя строка, и оставить старшее слагаемое. Вложенный цикл это умножение, только если внутренний не зависит от внешнего; когда зависит, как во втором примере, считают сумму, и она чаще всего даёт тот же порядок, что и умножение.

Худший, средний и амортизированный случай

O-нотация отвечает на вопрос «как растёт время с ростом N», но не говорит, на каких данных. Одна и та же операция бывает быстрой почти всегда и медленной на редком входе, поэтому у сложности три оси, а не одна.

Худший случай считают по самому неудобному входу: быстрая сортировка на уже отсортированном массиве с неудачным опорным элементом делает O(N²) сравнений, хотя обычно O(N log N). Средний случай считают по типичным данным: для той же сортировки O(N log N), для поиска в хеш-таблице O(1). Когда пишут «хеш-таблица: O(1)», имеют в виду среднее; худшее там O(N), если все ключи попали в одну корзину. Библиотеки защищаются от этого по-разному: Java превращает переполненную корзину HashMap в дерево, чтобы худшее стало O(log N), а Go, Python и JavaScript подмешивают в хеш случайное число при старте, чтобы плохие ключи нельзя было подобрать нарочно.

Третья ось, амортизированная сложность, про серию операций, а не про одну. Добавление в конец динамического массива (ArrayList в Java, append к срезу в Go, push в JavaScript, list.append в Python) почти всегда стоит O(1), но раз в несколько тысяч вызовов массив заполняется, и его копируют в новый, больший, за O(N). Копирование редкое ровно настолько, что на N вставок в сумме уходит O(N) работы, то есть O(1) на вставку в среднем по серии. Это и называют амортизированным O(1): отдельная операция бывает дорогой, но дорогие оплачены дешёвыми до неё.

О чём говорить в каждом случае: для ответа пользователю важен худший случай (одна долгая операция это зависший экран), для пакетной обработки средний и амортизированный (важна сумма). Поэтому в таблице сложностей рядом со структурой всегда стоит пометка, какой случай имеется в виду; без неё O(1) у хеш-таблицы и O(1) у массива не одно и то же обещание.

Сложность по памяти

Той же нотацией меряют не только время, но и дополнительную память, которую алгоритм просит сверх входных данных. Обход массива двумя указателями обходится несколькими переменными, это O(1) по памяти. Сортировка слиянием держит копию массива, O(N). Таблица динамического программирования на два измерения, O(N·M).

Считают именно дополнительную память: сам входной массив не в счёт, иначе всё было бы O(N). Рекурсия тоже стоит памяти, хотя массива в коде не видно: каждый незавершённый вызов лежит в стеке, и рекурсивный обход списка из миллиона узлов это O(N) памяти и переполнение стека вызовов. Когда две реализации равны по времени, выбирают по памяти: сортировка вставками на месте против слияния с копией, хеш-таблица с цепочками против открытой адресации.

Коротко

• Степень 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²).
• N·log N — это почти линейно. На миллионе элементов это всего в 20 раз дороже N и в 50 000 раз дешевле N².
• Мерка работает на больших N. На сотне элементов быстры все; разрыв между O(N) и O(N²) проявляется на росте данных, поэтому константы и отбрасывают.
• У сложности три оси: худший случай, средний и амортизированный по серии операций; «O(1)» у хеш-таблицы среднее, у добавления в конец динамического массива амортизированное.
• O-нотацией меряют и дополнительную память: рекурсия глубиной N это O(N) в стеке.
• 2ⁿ в задачах это перебор подмножеств (каждую вещь берут или нет), N! это перебор порядков; «все наборы» в условии значит маленькое N или приём, сокращающий перебор.
• Порядок роста по коду: считают, сколько раз выполнится самая внутренняя строка; вложенный цикл это умножение, зависимый внутренний цикл это сумма с тем же старшим слагаемым.

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

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