Що таке складність алгоритму — Структури даних і алгоритми

Коли ви обираєте алгоритм, важливо не лише «чи працює», а й «як швидко росте час роботи, коли даних стає більше». Велике О описує верхню межу зростання: як змінюється кількість кроків відносно розміру вхідних даних $n$ . Це не секунди на годиннику — це тренд. Уявіть два ліфти в будинку: один піднімає по одному поверху за раз, інший — одразу на потрібний. На другому поверсі різниці майже немає; на сотому — величезна. Так само $O(n)$ і $O(n^2)$ можуть виглядати однаково на маленьких тестах, але обмеження на LeetCode розводять їх жорстко.

Складність оцінюють за кількістю елементарних операцій: порівнянь, присвоєнь, звернень до масиву. Константи і дрібні деталі реалізації відкидають — нас цікавить порядок зростання, коли $n$ стає дуже великим. Тому два алгоритми з однаковим великим О можуть відрізнятися в реальному часі, але на співбесіді спочатку називають клас складності, а вже потім обговорюють оптимізації.

Найкращий, середній і найгірший випадок

Один і той самий код може поводитися по-різному. Найкращий випадок — найкращий сценарій (наприклад, елемент одразу знайшли). Найгірший — найгірший (елемент у кінці або його немає). Середній — типовий сценарій. На співбесідах і в задачах з LeetCode зазвичай мають на увазі найгірший випадок, якщо не сказано інакше.

Приклад

Лінійний пошук у масиві довжини $n$ : найкращий випадок $O(1)$ (знайшли на першій позиції), найгірший $O(n)$ (перевірили всі елементи). Сортування злиттям має $O(n \log n)$ у всіх трьох випадках — стабільна поведінка. Середній випадок лінійного пошуку — теж $O(n)$ , якщо елемент може бути на будь-якій позиції з однаковою ймовірністю. На практиці найгірший випадок часто важливіший: підступні тести на платформах якраз підбирають найгірший вхід.

Поширені класи великого О

$O(1)$ — константний час: доступ до елемента масиву за індексом. $O(\log n)$ — кожен крок ділить задачу навпіл: бінарний пошук у відсортованому масиві. $O(n)$ — один прохід по даних. $O(n \log n)$ — типово для ефективного сортування. $O(n^2)$ — вкладені цикли по $n$ : наївне порівняння кожної пари.

Порада

Порівнюйте класи за зростанням: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$ . Якщо $n = 10^6$ , різниця між $O(n)$ і $O(n^2)$ — мільйон проти трильйона операцій. Корисна евристика: за секунду сучасний сервер встигає приблизно $10^8$ простих операцій. $n = 10^5$ з $O(n^2)$ дає $10^{10}$ — це перевищення ліміту часу. Тримайте цю таблицю в голові перед вибором наївного перебору.

Не плутайте простір і час. Складність за памʼяттю описує додаткову памʼять: новий масив, словник, глибину стека рекурсії. Алгоритм може бути $O(n)$ за часом і $O(1)$ за памʼяттю (на місці), або навпаки — $O(n \log n)$ за часом сортування і $O(n)$ за памʼяттю для копії. На співбесіді часто питають обидва показники.

Підрахунок кроків у циклах

Один цикл по $n$ — близько $n$ кроків, $O(n)$ . Два вкладені — близько $n^2$ , $O(n^2)$ . Цикл, що щоразу ділить діапазон навпіл, дає $O(\log n)$ . Константи всередині (два проходи замість одного) на клас Big O не впливають. Намалюйте таблицю для $n = 10, 100, 1000$ : лінійний ріст лишається «читабельним», квадратичний одразу вибухає.

Типовий фрагмент

Три функції рахують кроки для різних $n$ — інтуїція класів складності. Код нижче лише для читання; писати й запускати розвʼязки задач ви будете на LeetCode.

Python

def tally_constant(size):
    ops = 0
    ops += 1
    return ops

def tally_linear(size):
    ops = 0
    for idx in range(size):
        ops += 1
    return ops

def tally_quadratic(size):
    ops = 0
    for i in range(size):
        for j in range(size):
            ops += 1
    return ops

for n in [10, 100, 1000]:
    print(n, tally_constant(n), tally_linear(n), tally_quadratic(n))

Вивід

Натисніть «Запустити» — вивід зʼявиться тут

Увага

Велике О ігнорує константи: $O(2n)$ записують як $O(n)$ . Нижчі доданки відкидають: $O(n^2 + n)$ — це $O(n^2)$ .

Що запамʼятати

Велике О описує зростання в найгіршому випадку. Знайте базові класи й умійте оцінити вкладені цикли. Після кожної задачі проговоріть складність вголос.