1. Введение
Представьте, что вы написали программу: она выводит правильный ответ, компилятор не ругается, и вы уже почти готовы праздновать. И тут кто-то приносит входные данные не из трёх чисел, а из трёх миллионов. В этот момент выясняется, что «работает» и «работает быстро» — это две разные истории.
Сложность (Big‑O) — это не про микросекунды и не про «мой ноутбук мощный», а про то, как растёт количество действий, когда растёт размер входа.
Пока мы учимся, нам важнее всего научиться видеть опасные места: например, два вложенных цикла, которые на маленьких числах выглядят мило, а на больших превращаются в «почему вентилятор орёт, как турбина самолёта».
Что считаем и что такое N
Чтобы говорить про O(…), нам нужен параметр N — размер входа. Слово «размер» здесь не обязательно означает байты или мегабайты; чаще это просто «сколько элементов», «сколько чисел», «сколько строк», «до какого числа идём».
Мы не будем измерять время секундомером — вместо этого будем считать, сколько раз выполняется «типичное действие» (например, тело цикла). Такой подсчёт грубый, но он отлично показывает, почему одна и та же идея на больших входах ведёт себя по-разному.
Важно: мы не ищем точную формулу вроде «1342 операции». Мы ищем характер роста. Если при увеличении N в 10 раз число действий увеличивается примерно в 10 раз — это один тип роста. Если увеличивается примерно в 100 раз — это уже совсем другой характер.
2. Один цикл: O(N)
Один цикл, который пробегает от 0 до N (или от 1 до N), обычно даёт линейный рост: «примерно N повторений». Это называют O(N) и читают как «порядка N». Это значит: если N вырос в 10 раз, то и работы стало примерно в 10 раз больше. Не в 9.7 и не в 10.3 — нам сейчас важна именно грубая картина.
Давайте не просто поверим на слово, а сделаем маленький «счётчик действий» — переменную, которую будем увеличивать в теле цикла. Это не измерение времени, но честный способ увидеть, сколько раз цикл реально сработал.
Пример: “посчитать”, сколько раз выполняется тело for
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
int ops = 0;
for (int i = 0; i < n; i = i + 1) {
ops = ops + 1; // считаем "одно действие"
}
std::cout << ops << '\n'; // при n=5 будет 5
}
Здесь ops в конце будет примерно равен n. Если n = 1000, будет 1000. Если n = 1'000'000, будет миллион. Линейно, честно, без сюрпризов.
Мини-таблица для ощущения масштаба
Пока без математики — просто как «чувство числа»:
| N | Примерно сколько раз выполнится тело (O(N)) |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
| 10 000 | 10 000 |
На этом месте обычно появляется уверенность: «ну, один цикл — это не страшно». И часто это правда. Проблемы начинаются, когда мы перемножаем количество повторений.
3. Вложенные циклы: O(N²)
Самый важный момент: когда один цикл находится внутри другого, внутренний выполняется на каждом шаге внешнего. Если внешний делает N шагов, и на каждом шаге мы ещё делаем N шагов внутри — получится примерно N · N, то есть N².
Почему это важно: если N вырос в 10 раз, то N² вырастет примерно в 100 раз. Увеличили вход «немножко» — программа стала «внезапно» очень медленной.
Пример: считаем количество пар (i, j)
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
}
}
std::cout << ops << '\n'; // при n=3 будет 9
}
Если n = 3, получаем 9. Если n = 10, будет 100. Если n = 1000, будет уже 1 000 000. Тут рост ощущается гораздо сильнее.
Визуальная схема: почему получается умножение
Чтобы мозг перестал считать это магией, можно представить так:
Идея простая: «внутренний цикл полностью прокручивается для каждого i». Поэтому и умножение.
Мини-таблица для квадратичного роста
| N | Примерно сколько раз выполнится тело (O(N²)) |
|---|---|
| 10 | 100 |
| 100 | 10 000 |
| 1000 | 1 000 000 |
| 10 000 | 100 000 000 |
И вот на 10 000 уже не до шуток: сто миллионов повторений — это может быть заметно даже на хорошем компьютере, а на учебной платформе или слабом окружении — тем более.
Когда внутренний цикл не до N: “треугольник”, но всё равно O(N²)
Иногда студенты видят код вроде for (j = 0; j < i; ++j) и надеются, что раз внутренний цикл «короче», то и сложность уже не квадратичная. На самом деле часто это всё равно квадратичный рост, просто коэффициент меньше.
Внутренний цикл сначала короткий, потом всё длиннее и длиннее — и суммарно набирается примерно «половина квадрата». Мы сейчас не будем доказывать формулами, но на уровне интуиции это хорошо чувствуется: при больших N внутренняя работа всё равно растёт примерно как N².
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < i; j = j + 1) {
ops = ops + 1;
}
}
std::cout << ops << '\n'; // при n=4 будет 6
}
При n = 4 внутренний цикл делает 0 + 1 + 2 + 3 = 6 шагов. При n = 5 будет 10. Это растёт примерно как «квадрат», просто не полный квадрат, а «треугольник».
4. Константы, несколько проходов и break
Когда мы говорим O(…), мы обычно игнорируем мелкие детали: «плюс 5 действий», «плюс 2» и даже «умножить на 2». Это не потому, что математики вредные, а потому что при больших N эти добавки не меняют характер роста.
Например, два цикла подряд по N итераций — это примерно 2N действий, но рост всё равно линейный: N увеличили в 10 раз, 2N тоже увеличится в 10 раз.
Отдельная практическая деталь: в документации и обсуждениях стандартной библиотеки C++ сложность принято записывать именно в терминах роста (например, выражениями вида N·logN), потому что важен порядок, а не «плюс-минус 17 операций».
Два независимых линейных цикла: всё ещё O(N)
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
int ops = 0;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
std::cout << ops << '\n'; // при n=3 будет 6
}
Вложенный цикл “побеждает” несколько линейных
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) ops = ops + 1;
}
std::cout << ops << '\n'; // при n=100 будет 10000
}
Даже если вы добавите «ещё два линейных цикла», основной вклад будет от N², потому что N² растёт намного быстрее.
break спасёт? Иногда ускорит запуск, но не отменит структуру
Очень хочется сказать: «Ну ладно, у меня два вложенных цикла, но я внутри делаю break, значит всё хорошо». Иногда это действительно ускоряет конкретный запуск. Но Big‑O чаще всего рассказывает про рост работы «в целом» и обычно ориентируется на худший сценарий по росту.
Если break срабатывает рано — хорошо. Если не срабатывает (или срабатывает поздно) — вы всё равно получите почти полный квадрат. Поэтому полезная привычка такая: break может помочь, но структура «N раз по N» остаётся подозрительной, пока вы не понимаете, когда именно будет выход.
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
bool found = false;
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
if (i == n - 1 && j == n - 1) { // "нашли" в самом конце
found = true;
break;
}
}
if (found) break;
}
std::cout << ops << '\n'; // почти n*n
}
5. Практический пример: “LoopLab” для экспериментов
Чтобы тема не осталась в виде философии, соберём небольшой «стенд» — программу, которая позволяет ввести n и посмотреть, сколько «шагов» делают разные конструкции: линейная, квадратичная и треугольная.
Мы не делаем настоящий профилировщик: просто считаем итерации и печатаем числа. Такой подход в учебных задачах даёт ощущение масштаба без сложных инструментов.
Сделаем простое меню через if/else (мы ещё не проходили switch, поэтому не используем его).
Каркас “LoopLab” с выбором режима
#include <iostream>
int main() {
int mode = 0;
int n = 0;
std::cin >> mode >> n; // например: "2 100"
if (mode == 1) {
int ops = 0;
for (int i = 0; i < n; i = i + 1) ops = ops + 1;
std::cout << ops << '\n';
} else if (mode == 2) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1)
for (int j = 0; j < n; j = j + 1) ops = ops + 1;
std::cout << ops << '\n';
} else {
std::cout << "Unknown mode\n";
}
}
Уже можно играться: режим 1 показывает O(N), режим 2 — O(N²).
Добавим “треугольник” как режим 3
#include <iostream>
int main() {
int mode = 0, n = 0;
std::cin >> mode >> n;
if (mode == 3) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1)
for (int j = 0; j < i; j = j + 1) ops = ops + 1;
std::cout << ops << '\n';
}
}
Теперь, если вы введёте 3 5, увидите 10, а если 3 1000, увидите 499500 — число уже большое, и оно растёт примерно «как квадрат».
Режим 4: “квадрат, но иногда выходим раньше”
#include <iostream>
int main() {
int mode = 0, n = 0;
std::cin >> mode >> n;
if (mode == 4) {
long long ops = 0;
for (int i = 0; i < n; i = i + 1) {
for (int j = 0; j < n; j = j + 1) {
ops = ops + 1;
if (i == 0 && j == 0) break; // выходим очень рано
}
}
std::cout << ops << '\n'; // при любом n будет n (по 1 шагу на строку)
}
}
Здесь интересная мысль: структура вроде бы вложенная, но break делает так, что на каждой итерации внешнего цикла выполняется ровно один шаг внутреннего. В итоге получается примерно N, то есть «на практике линейно».
Это хороший повод помнить, что O(…) — это язык описания роста, а не магическая печать «плохо/хорошо».
6. Типичные ошибки
Ошибка №1: путать N с “значением”, а не с “размером”.
Очень частая путаница: студент пишет цикл до n, но потом думает о n как о «самом числе», а не как о «размере входа». Например, если n — это количество элементов, то N — именно «сколько элементов», а не «какие они». В сложности нас интересует рост по количеству, иначе мы сравниваем несравнимое.
Ошибка №2: пытаться считать “каждую операцию процессора” и утонуть в деталях.
На первом знакомстве с O(…) легко начать спорить с собой: «А сравнение — это тоже операция? А i = i + 1 — это одна или две?» Если вы так делаете — вы нормальный человек, просто мозг любит точность. Но Big‑O сейчас про другое: считать надо не микрошаги, а сколько раз повторяется основной кусок работы.
Ошибка №3: не замечать вложенность, потому что код “короткий”.
Два цикла могут быть записаны очень компактно, особенно если без фигурных скобок. Из-за этого визуально кажется, что «там всего две строчки». На практике это может быть миллион итераций внутри миллиона. В учебном коде лучше сознательно ставить {} и форматировать вложенность так, чтобы глаз сразу видел: «это цикл внутри цикла».
Ошибка №4: верить, что break автоматически превращает O(N²) в O(N).
break действительно может сильно ускорить запуск, но всё зависит от того, когда он сработает. Если «ответ» почти всегда находится быстро — да, в среднем код может вести себя почти линейно. Если же часто приходится проходить почти весь внутренний цикл — вы снова получаете почти квадрат. Поэтому break — не амнистия, а инструмент, который нужно понимать.
Ошибка №5: off-by-one в границах и неправильные выводы о росте.
Если вы случайно написали i <= n вместо i < n, вы добавили всего одну итерацию, и порядок роста не изменится. Но на маленьких N вы можете получить «странные числа» и начать сомневаться в идее. Поэтому, когда вы проверяете такие вещи, полезно прогонять пример на совсем маленьких N (0, 1, 2, 3) и смотреть, совпадает ли смысл.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ