Згадуємо Big‑O

1. Вступ

Коли ви лише починаєте програмувати, здається, що швидкість — це щось для «дуже великих компаній» і «дуже великих серверів». Насправді все простіше: ви можете написати консольний застосунок, який на 100 елементах літає, а на 100 000 починає замислено дивитися в стіну. І найприкріше — він при цьому не ламається, помилок немає, просто «чомусь став повільним».

Big‑O — це спосіб заздалегідь зрозуміти, як алгоритм або операція масштабується, тобто що станеться, коли даних побільшає. Він не обіцяє точних мілісекунд, зате чесно відповідає на запитання: «Якщо N збільшиться в 10 разів, час виконання зросте приблизно в 10 разів, у 100 разів чи майже не зміниться?». Для розробника це як уміння читати прогноз погоди: воно не гарантує сонця, але допомагає не вийти в шортах у січні.

Big‑O на пальцях: що таке N і чому ми «не помічаємо» константи

Big‑O описує, як зростає вартість залежно від розміру вхідних даних. Розмір входу зазвичай позначають N: кількість елементів у контейнері, довжина рядка, кількість запитів — загалом, «скільки даних ми обробляємо». Коли кажемо O(N), це означає: «якщо N збільшиться в 2 рази, то роботи стане приблизно в 2 рази більше». Коли кажемо O(N²), це означає: «якщо N збільшиться в 2 рази, роботи стане приблизно в 4 рази більше» — і ось тут уже не до жартів.

Важливо зрозуміти одну річ: Big‑O свідомо ігнорує константи та «дрібні поліпшення». Якщо у вас два алгоритми O(N), але один у 2 рази швидший, Big‑O скаже: «Вони однакові». І це нормально: Big‑O говорить не про конкретний компʼютер, а про тенденцію зростання.

Нижче — невелика «мапа місцевості», щоб було легше орієнтуватися:

O(1)

O(log N)

O(N)

O(N²)

І ще один нюанс, який часто пропускають: ми оцінюємо не «весь контейнер», а конкретну операцію. Навіть у тому самому std::vector v[i] і v.insert(v.begin(), x) — це два зовсім різні світи за вартістю.

2. Доступ до елемента: індекс, «взяти i‑й» і чому list не дружить із []

Коли ви пишете v[i], ви очікуєте, що доступ буде швидким. У std::vector це очікування виправдане: елементи лежать «щільно», і адресу i‑го елемента можна обчислити одразу. У std::deque теж є operator[], і такий доступ зазвичай вважають O(1) в інтуїтивній моделі: усередині там блоки, але інтерфейс дає випадковий доступ.

А от std::list влаштований як ланцюжок вузлів: щоб дійти до i‑го, потрібно пройти i кроків за посиланнями. Тому в списку немає operator[] — не тому, що розробники STL «забули», а тому, що це був би дуже підступний інтерфейс: виглядав би як швидкий доступ, а насправді був би лінійним проходом.

Уявімо, що в нашому навчальному застосунку TaskFlow (мінітрекері задач) ми хочемо «показати 5‑ту задачу». Для vector це природно, для list — ні.

#include <iostream>
#include <vector>
#include <string>

struct Task {
    int id{};
    std::string title{};
};

int main() {
    std::vector<Task> tasks{{1, "Read"}, {2, "Code"}, {3, "Sleep"}};

    std::cout << tasks[1].title << '\n'; // Code
}

А тепер той самий зміст для list — уже через ітератор і std::next:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

struct Task {
    int id{};
    std::string title{};
};

int main() {
    std::list<Task> tasks{{1, "Read"}, {2, "Code"}, {3, "Sleep"}};

    auto it = std::next(tasks.begin(), 1); // пройти 1 крок уперед
    std::cout << it->title << '\n';        // Code
}

За Big‑O різниця така: доступ vector[i] — це майже константна операція, а «дійти до i‑го в list» — це лінійна робота, тобто в найгіршому разі O(N).

І тут важлива думка: «доступ до елемента» — це не лише читання, а й те, як часто ви його виконуєте. Якщо ви в циклі багато разів берете елемент list за «номером», то не просто робите O(N) — ви часто випадково будуєте O(N²).

3. Вставка: кінець, початок, середина — три різні сценарії з різною ціною

Слово «вставка» звучить однаково, але реальна вартість залежить від того, куди і в який контейнер ви вставляєте. Для новачка це найчастіша пастка: «Я додаю елемент, чому це раптом повільно?» — тому що «додати» може означати зовсім різні речі.

Почнімо з найприємнішого: додати в кінець.

У std::vector push_back зазвичай розглядають як амортизоване O(1): найчастіше це просто покласти елемент у вільне місце, а іноді — дороге розширення буфера. У std::deque додавання в кінець теж природна операція, і вона зазвичай поводиться стабільно. У std::list вставка за наявним ітератором узагалі дешева, але цей ітератор ще треба мати.

Приклад: додамо задачу в кінець списку задач.

#include <iostream>
#include <vector>
#include <string>

struct Task {
    int id{};
    std::string title{};
};

int main() {
    std::vector<Task> backlog;
    backlog.push_back({1, "Write report"});
    backlog.push_back({2, "Fix bug"});

    std::cout << backlog.size() << '\n'; // 2
}

Тепер «неприємний» варіант: вставка на початок.

Для vector вставка на початок означає, що всі елементи потрібно зсунути праворуч, щоб звільнити місце на нульовому індексі. Це типовий O(N) за кількістю елементів. Для deque вставка на початок — «рідна» операція (push_front) і зазвичай розглядається як O(1) на рівні інтуїції. Для list вставка на початок теж дешева (push_front), бо це просто додати новий вузол.

#include <iostream>
#include <deque>
#include <string>

struct Task {
    int id{};
    std::string title{};
};

int main() {
    std::deque<Task> urgent;
    urgent.push_front({1, "PROD is on fire"}); // так, так і назвемо
    urgent.push_front({2, "CEO asks: why?"});

    std::cout << urgent.front().title << '\n'; // CEO asks: why?
}

Тепер третій випадок — вставка всередину.

Тут важливо мислити у два етапи. Якщо у вас vector, то вставка всередину знову означає зсуви, тобто O(N) (приблизно «розмір хвоста»). Якщо у вас list, то сама вставка «за ітератором» дешева (O(1)), але знайти цей ітератор зазвичай коштує O(N), якщо ви шукаєте лінійно. Тобто list пришвидшує вставку, але не обовʼязково пришвидшує пошук місця.

Мініприклад: вставимо задачу перед другою.

#include <iostream>
#include <list>
#include <string>

struct Task {
    int id{};
    std::string title{};
};

int main() {
    std::list<Task> tasks{{1, "A"}, {2, "C"}};

    auto it = std::next(tasks.begin(), 1); // позиція на "C"
    tasks.insert(it, {3, "B"});            // вставка перед "C"

    for (const auto& t : tasks) {
        std::cout << t.title << ' ';
    }
    std::cout << '\n'; // A B C
}

Тут вставка сама по собі дешева, але зверніть увагу: ми вже «знали» позицію, тобто мали ітератор. Якби ми шукали її за назвою, довелося б пройти список.

4. Видалення: pop_back, erase і «плата за зсув»

Видалення — брат-близнюк вставки: його ціна теж залежить від місця й контейнера. Новачки часто вважають, що «видалити елемент» — це просто «прибрати його зі структури». Для вузлових контейнерів це ближче до правди. Для масивоподібних контейнерів видалення часто означає ще й «закрити порожнє місце».

Найпростіший випадок — видалити з кінця.

У vector pop_back() зазвичай має O(1): просто зменшуємо розмір, а деструктор елемента викликається, якщо це потрібно. У deque pop_back() теж природна операція. У list pop_back() — так само.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};
    v.pop_back();

    std::cout << v.size() << '\n'; // 2
}

Видалення з початку.

У deque pop_front() — рідна операція. У vector прямого pop_front() немає, бо це означало б зсунути всі елементи на одну позицію ліворуч, тобто O(N). Можна зробити erase(begin()), але це той самий зсув, просто під іншою назвою.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> q{10, 20, 30};
    q.pop_front();

    std::cout << q.front() << '\n'; // 20
}

Видалення із середини.

У vector видалення erase(it) призводить до зсуву хвоста ліворуч, тобто O(N). У list видалення за ітератором — локальна операція, зазвичай її розглядають як O(1), але ітератор має бути валідним і, знову ж таки, пошук ітератора може коштувати O(N).

Невеликий фрагмент «TaskFlow»: видаляємо всі виконані задачі (наприклад, із парним id) безпечним способом. Тут саме Big‑O підказує нам, що vector.erase усередині проходу може бути дорогим, бо кожен erase потенційно зсуває хвіст.

#include <vector>

int main() {
    std::vector<int> ids{1, 2, 3, 4, 5};

    for (auto it = ids.begin(); it != ids.end(); ) {
        if (*it % 2 == 0) {
            it = ids.erase(it); // зсув елементів ліворуч
        } else {
            ++it;
        }
    }
}

Навіть якщо код виглядає коротким, за великої кількості видалень ціна може бути високою. І це не «тому що STL погана», а тому, що ви просите масивоподібну структуру постійно перебудовувати «щільний ряд» елементів.

5. Шпаргалка: контейнери й адаптери

Таблиця вартості операцій

Коли ви навчаєтеся, мозку потрібно кілька «якорів». Таблиця нижче — це радше якір, а не юридичний документ. Вона допомагає швидко оцінити вартість операцій для основних контейнерів і не чекати від list поведінки масиву, а від vector — поведінки двобічної черги.

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(N)

O(N)

O(N)

Зверніть увагу на останній рядок: пошук позиції майже всюди лінійний, якщо ви шукаєте «вручну». Тому корисно міркувати так: «скільки коштує знайти місце» + «скільки коштує вставити або видалити, коли місце вже знайдено».

Адаптери й Big‑O

Контейнерні адаптери зручні тим, що вони одразу задають стиль роботи з даними. У них менше методів, але саме тому легше дотримуватися дисципліни: ви не зробите випадково «вставку всередину стека», бо такої операції просто немає.

std::stack і std::queue в інтуїтивній моделі дають операції push/pop константної вартості. Це логічно: стек працює з вершиною, черга — з початком і кінцем. Ви рідко думаєте про Big‑O, коли використовуєте стек, бо інтерфейс уже «змушує» виконувати дешеві операції.

std::priority_queue трохи цікавіша: вона підтримує «найкращий елемент» на вершині, тому top() зазвичай сприймається як O(1), а push/pop — як O(log N), бо потрібно підтримувати структуру «купи».

Мініприклад для нашого TaskFlow: нехай у задачі є пріоритет, і ми хочемо щоразу брати найтерміновішу.

#include <queue>
#include <string>
#include <iostream>

struct Task {
    int priority{};
    std::string title{};
};

int main() {
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(10);
    pq.push(7);

    std::cout << pq.top() << '\n'; // 10
}

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

6. Як прикинути складність сценарію

Коли ви вибираєте контейнер, ви насправді вибираєте, які операції будуть дешевими, а які — дорогими. Щоб це перестало бути «магією», корисно мислити через профіль операцій. Уявіть, що TaskFlow виконує типовий цикл: додали задачу, інколи вставили термінову на початок, інколи видалили виконану із середини.

Спрощена схема міркування така:

flowchart TD
    A[Визначити найчастіші операції] --> B[Для кожної операції оцінити Big‑O]
    B --> C[Оцінити загальне зростання: скільки разів виконується кожна операція]
    C --> D[Порівняти контейнери за найдорожчими операціями]

На практиці це виглядає майже як «арифметика для людей». Якщо ви знаєте, що у вас буде приблизно N задач і ви будете K разів вставляти на початок, то vector уже викликає підозру: вставка на початок має O(N), і сумарно ви отримаєте щось близьке до O(K·N) вже тільки на цій ділянці. А якщо K теж зростає разом із N, то можна непомітно доїхати до квадратичного зростання.

Добра звичка — ставити собі запитання: «Що в моєму коді відбувається найчастіше?». Якщо найчастіше ви просто додаєте в кінець і проходите лінійно, vector майже завжди виглядає розумним вибором. Якщо у вас багато операцій на обох кінцях, частіше згадують про deque. Якщо у вас є часті вставки й видалення за вже знайденими позиціями (наприклад, ви зберігаєте ітератори на «активні» елементи), тоді вузлова структура на кшталт list може мати сенс.

І так, іноді правильна відповідь звучить нудно: «Давайте залишимо vector, бо у нас реально 200 елементів, і все». Big‑O не забороняє прості рішення; він забороняє сліпу впевненість в тому, що «один рядок коду завжди дешевий».

7. Типові помилки під час оцінювання Big‑O

Помилка №1: плутати «операцію на контейнері» і «сценарій із багатьох операцій».
Часто дивляться на один рядок (erase, insert) і думають: «Ну це ж одна команда». Але насправді така команда може зсунути десятки тисяч елементів. Корисна звичка — подумки уявити, що відбувається з рештою елементів: їх треба зсувати чи ні.

Помилка №2: вважати, що list автоматично робить усе швидко, бо «вставка O(1)».
Так, вставка за ітератором дешева, але ітератор не зʼявляється з повітря. Якщо ви спочатку шукаєте місце лінійним проходом, то все одно платите O(N) за пошук. У підсумку прискорення буде лише в тій частині, де ви справді багато вставляєте або видаляєте за вже відомими позиціями.

Помилка №3: не розрізняти «видалити» і «видаляти багато разів».
Один erase у vector може бути ще прийнятним. Тисяча erase усередині, особливо в циклі, може перетворити день на ніч (а ноутбук — на обігрівач). Якщо видалень багато, варто хоча б замислитися: чи не краще спочатку побудувати новий контейнер без елементів, які треба прибрати, ніж тисячу разів рухати хвіст.

Помилка №4: чекати від deque поведінки «поліпшеного vector у всьому».
deque добрий в операціях на кінцях, але це не означає, що він завжди виграє в будь-яких вставках чи видаленнях усередині. Якщо ви часто вставляєте всередину, то все одно платитимете за переміщення або перебудову. Контейнер вибирають під конкретні операції, а не за принципом «ну він звучить солідніше».

Помилка №5: думати, що Big‑O — це точний час у мілісекундах.
Big‑O не каже, що буде «рівно 12.3 ms». Він каже, як зростає ціна зі зростанням N. Це компас, а не GPS‑трекер. Використовуйте його, щоб не заблукати на великих N, а не щоб сперечатися, яка реалізація швидша на наборі з 7 елементів.

1

Опитування

Видалення під час обходу, рівень 59, лекція 4

Недоступний

Видалення під час обходу

Видалення під час обходу

Відкрити