Нотация Big O («О» большое) — это способ описания производительности функции без измерения времени ее выполнения. Вместо того, чтобы засекать, сколько секунд выполняется функция от начала до конца, Big O показывает, как меняется время ее выполнения по мере увеличения размера входных данных. Этот подход помогает понять, как программа будет вести себя при разных объемах входящей информации.

В этой статье я разберу четыре наиболее часто встречающиеся категории нотации Big O: константную, логарифмическую, линейную и квадратичную. Не переживайте, если эти термины пока ничего вам не говорят — мы подробно рассмотрим каждый из них и наглядно визуализируем в процессе.

Прим. пер.: в оригинальной статье много прикольных интерактивных элементов, которые, к сожалению, нельзя перенести на Хабр. Я постарался сделать максимально информативные скриншоты, но для пущего эффекта рекомендую обратиться к оригиналу.

❯ Итерация

Рассмотрим функцию на JavaScript, которая вычисляет сумму чисел от 1 до n:

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

Я передам в функцию 1 миллиард, используя сокращенную запись 1e9, чтобы выполнение заняло заметное время. При запуске функции мы узнаем, сколько времени потребуется на вычисление суммы чисел от 1 до 1 миллиарда:

На моем ноутбуке это занимает чуть меньше 500 миллисекунд. Как показано выше, полученное время может отличаться, и при каждом запуске варьируется на несколько десятков миллисекунд — так и должно быть.

Измерение времени выполнения кода таким способом — когда фиксируется момент начала и конца, а затем вычисляется разница — называется вычислением "реального времени" (wall-clock time).

Как думаете, сколько потребуется на вычисление 2 миллиардов, 2e9?

Это занимает примерно в два раза больше времени. Код выполняет цикл n раз и на каждом шаге выполняет одно сложение. Если передать 3 миллиарда, время выполнения, вероятно, увеличится в три раза.

Связь между размером входных данных функции и временем ее выполнения называется временной сложностью (time complexity), а нотация Big O — это способ, с помощью которого мы описываем временную сложность функции.

Ниже показан пример с разными значениями n, передаваемыми в функцию sum: кнопка 1e9 вызывает sum(1e9), кнопка 2e9 — sum(2e9) и т.д. На них видно, что при 1e9 функция выполняется быстро, при 2e9 — примерно вдвое дольше, а при 3e9 — примерно втрое дольше. Каждое увеличение на 1 миллиард приводит к соответствующему росту времени выполнения.

Поскольку реальное время выполнения sum() растет с той же скоростью, что и n (например, sum(20) работает примерно вдвое дольше, чем sum(10)), мы называем sum линейной функцией. Ее сложность выражается как O(n).

Почему мы используем именно такой синтаксис: O(n)? Что означает буква O? Зачем нужны скобки?

Буква O означает order — «порядок», сокращение от «порядок роста». Иными словами, это читается как «порядок роста функции sum равен n». Запись O(n) — это компактный способ выразить эту идею. Нотацию ввел немецкий математик Пауль Бахман еще в 1894 году. Кстати, буква O (английская «о») в некоторых шрифтах может выглядеть как цифра 0, но всегда имеется в виду именно буква.

Другой способ посчитать сумму чисел от 1 до n — воспользоваться формулой (n*(n+1))/2. Вот что получится для чисел от 1 до 5. В каждом случае результат совпадает с «ручным» сложением, например 1+2+3+4+5 при n=5:

• (1×2)/2 = 2/2 = 1

• (2×3)/2 = 6/2 = 3

• (3×4)/2 = 12/2 = 6

• (4×5)/2 = 20/2 = 10

• (5×6)/2 = 30/2 = 15

Вот как выглядела бы функция sum, если бы она использовала эту формулу вместо цикла:

function sum(n) {
  return (n * (n + 1)) / 2;
}

Как думаете, как будет меняться реальное время работы этой функции при увеличении n? В следующих двух примерах размер входных данных отличается в 100 раз:

Здесь нет ошибки. Обе функции выполняются практически мгновенно. Разница во времени объясняется не самой функцией sum, а особенностями браузера и общей непредсказуемостью работы компьютера. Если запустить каждый вариант несколько раз, можно заметить, что реальное время выполнения колеблется примерно вокруг одного и того же значения.

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

Ух ты, мы улучшили нашу функцию sum с O(n) до O(1)! Теперь она всегда выполняется мгновенно!

Верно. Но важно помнить: O(1) не всегда означает «мгновенно». Это лишь означает, что время выполнения не зависит от размера входных данных. В случае нашей новой функции sum, сумма действительно вычисляется почти моментально. Но в принципе алгоритм с O(1) может выполняться и минуты, и часы — все зависит от того, что именно он делает.

Кроме того, алгоритм с O(n) в некоторых случаях может оказаться быстрее, чем с O(1), если входные данные небольшие. Однако при росте размера входных данных именно O(1) в конечном итоге окажется эффективнее.

Пример этого эффекта можно увидеть на следующем графике:

Линия O(1) на графике все время находится на уровне 20, так почему же мы не пишем O(20)?

Назначение нотации Big O — описывать зависимость между размером входных данных и временем выполнения функции. Она не отвечает на вопрос, каким именно это время будет, а показывает лишь, как оно растет.

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

❯ Сортировка

Закончим с sum() и рассмотрим другой алгоритм — сортировку пузырьком (bubble sort).

Идея сортировки пузырьком проста: проходим по входному массиву и меняем местами соседние элементы, если они стоят в неправильном порядке. Продолжаем делать это до тех пор, пока не получится пройти по массиву без перестановок. Алгоритм получил такое название, потому что числа «всплывают» (bubble) на свои места, словно пузыри.

Ниже приведена реализация этого алгоритма на JS. Мы будем сортировать числа по возрастанию, поэтому ожидаемый результат: 1, 2, 3, 4, 5.

Теперь, когда вы увидели алгоритм в действии, как думаете, какова его временная сложность?

Если массив уже отсортирован, алгоритм проходит его один раз, не выполняет ни одной перестановки и завершает работу. Это соответствует O(n). Но если массив имеет любой другой порядок, придется проходить по нему несколько раз. В худшем случае, когда массив отсортирован в обратном порядке, придется пройтись по массиву n раз, чтобы переместить наименьший элемент с конца в начало.

Проход по n элементам массива n раз дает n*n операций, или n^2. Это значит, что сортировка пузырьком — алгоритм с O(n^2), это еще называют квадратичной временной сложностью.

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

Ниже показан еще один способ визуализировать сортировку пузырьком. Алгоритм начинается с массива [5, 4, 3, 2, 1] сверху вниз. В конце должен получиться массив [1, 2, 3, 4, 5] сверху вниз. Каждый шаг вперед соответствует полному проходу по массиву, который может включать несколько перестановок. Best, Worst и Rand — разные начальные конфигурации.

В случае Rand иногда хватает всего пары проходов. Несмотря на это, сортировка пузырьком все равно имеет сложность O(n^2), потому что в худшем случае придется пройти по массиву n раз.

❯ Поиск

Последний алгоритм, о котором я хочу рассказать — бинарный/двоичный поиск (binary search).

Начнем с небольшой демонстрации. Загадайте число от 1 до 100. Допустим, вы загадали 37. Алгоритм будет пытаться его угадать, а на скриншотах показано, как с помощью кнопок «больше» и «меньше» можно давать алгоритму подсказки, пока он не угадает число:

Lower -> Higher -> Correct!

Он начинает с середины диапазона (50) и с каждой подсказкой исключает половину оставшихся вариантов. Это и есть бинарный поиск.

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

Таблица ниже показывает последовательность угадываний для всех чисел от 1 до 100:

Если алгоритм на каждом шаге может исключать часть возможных вариантов, мы называем такую сложность логарифмической. Это значит, что бинарный поиск имеет временную сложность O(log n).

Ниже приведен график количества попыток, необходимых, чтобы угадать любое число от 1 до 1000:

Каждый раз, когда загаданное число удваивается, алгоритму требуется всего на одну попытку больше, чтобы его угадать. Если выбрать число от 1 до 1 миллиарда, понадобится максимум 31 попытка. Логарифмический рост очень медленный.

Ниже приведен график, сравнивающий его с O(n) и O(n^2), которые растут гораздо быстрее:

❯ Применяем знания на практике

В предыдущих разделах описывалась разница между алгоритмами O(1), O(log n), O(n) и O(n^2). Теперь давайте посмотрим на несколько ситуаций, с которыми можно столкнуться при написании кода, и разберем, что можно сделать для улучшения временной сложности.

Поиск элемента в списке

Ниже — функция для проверки наличия конкретного элемента в списке:

function contains(items, target) {
  for (const item of items) {
    if (item === target) {
      return true;
    }
  }
  return false;
}

Если приходится многократно искать элементы в одном и том же списке, стоит подумать об использовании структуры данных, которая обеспечивает более быстрый поиск, например Set. В современных браузерах Set реализован так, что поиск в нем имеет временную сложность O(1).

Однако не стоит делать так:

function contains(items, target) {
  const itemSet = new Set(items);
  return itemSet.has(target);
}

Создание new Set(items) — это операция со сложностью O(n)! Причина в том, что конструктор Set перебирает все элементы массива, добавляя их во множество. Следует соотносить затраты на эту начальную операцию с той выгодой, которую можно получить от ускоренного поиска.

const items = new Set(["apple", "banana", "cherry"]);
items.has("banana") // true, и это O(1)

Перебор массива по индексам

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

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

• Что можно сделать, чтобы ее улучшить?

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

Проблема в том, что внутри цикла вызывается indexOf(). А эта функция имеет сложность O(n)! Она проходит по массиву до тех пор, пока не найдет нужный элемент, и возвращает -1, если элемент не найден. Вызов indexOf() внутри цикла приводит к тому, что общая сложность функции buildList становится O(n^2).

Исправить это можно, перебрав массив с помощью индексов. Доступ к элементу массива по индексу имеет сложность O(1), поэтому общая временная сложность функции снижается до O(n):

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

То же самое можно сделать с помощью методов массивов forEach() или entries().

Кэширование промежуточных результатов

Рассмотрим функцию для вычисления факториала числа. В математике факториал записывают так: например, 5! означает 5*4*3*2*1, а 3! — 3*2*1.

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

Эта функция имеет временную сложность O(n), но большинство вызовов будет повторно выполнять уже проделанную работу. Например, вызов factorial(4), а затем factorial(5) приведет к тому, что factorial(4) будет вычислен дважды.

Чтобы избежать лишних вычислений, можно кэшировать результат каждого расчета:

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

В этом примере используется возможность выполнять поиск в Map за O(1). Это не уменьшает временную сложность функции факториала в наихудшем случае, но позволяет ускорить среднее время выполнения за счет увеличения расхода памяти.

Когда речь идет о производительности, важно помнить: нельзя слепо верить всему, что написано в интернете. Необходимо всегда тестировать код до и после изменений, чтобы убедиться, что производительность действительно улучшилась.

❯ Заключение

Подведем итоги:

• Нотация Big O описывает зависимость между входными данными функции и ее «реальным» временем выполнения.

• Рассмотренные примеры по росту времени выполнения:

  • O(1) — константное время (лучший вариант)

  • O(log n) — логарифмическое время

  • O(n) — линейное время

  • O(n^2) — квадратичное время

• Временную сложность кода можно улучшить, выбирая более эффективные алгоритмы и избегая распространенных ошибок.

Если эта статья вам понравилась, на моем сайте можно найти еще много похожих материалов. Я всегда рад получать вопросы и отзывы: можно писать на почту, связаться через Bluesky или анонимно через мой небольшой сервис ping.

И в завершение — последний график, сравнивающий все временные сложности, которые мы рассмотрели в этой статье:

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩