Big O

Зачем оценивать алгоритмы

Два решения одной задачи могут выдавать одинаковый результат, но вести себя совершенно по-разному, когда входных данных становится много. Одно почти не замечает роста входа, другое начинает выполнять в десятки или тысячи раз больше работы.

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

Что входит в раздел

• Основы сложности. Разберём, что считается размером входа, какие операции имеет смысл учитывать и зачем в оценке оставляют главное поведение алгоритма при росте данных.
• Временная сложность. Научимся оценивать количество работы по структуре кода и видеть, как циклы и повторяющиеся действия влияют на скорость роста.
• Пространственная сложность. Посмотрим не только на время, но и на дополнительную память, которую требует решение по мере увеличения входа.
• Основные классы сложности. Соберём типичные варианты роста — от почти постоянной работы до быстро растущих алгоритмов — и научимся узнавать их в коде.
• Амортизированная сложность. Разберём ситуации, где отдельная операция иногда дорогая, но длинная последовательность таких операций в среднем остаётся эффективной.
• Лучший, средний и худший случай. Научимся различать оценки одного алгоритма для разных входных данных и понимать, какую из них имеет смысл использовать в конкретном рассуждении.

От кода к оценке

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

int sum = 0;

for (int value : numbers) {
    sum += value;
}

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