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 |
| 1 000 | 1 000 |
| 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 |
| 1 000 | 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 << "Невідомий режим\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, побачите 499 500 — число вже велике, і воно зростає приблизно «як квадрат».
Режим 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) і дивитися, чи відповідає результат задуму.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ