Темпи зростання, а не абсолютні вартості
Big O: вимірювання темпів зростання вартості алгоритму
Нотація Big O вимірює темп зростання вартості алгоритму — не абсолютну вартість.
Питання, на яке відповідає Big O: коли розмір входу N подвоїться, чи подвоїться й робота? Чи учетверітиметься? Чи залишиться незмінною?
Буква 'O' означає 'порядок величини'. Вираз у дужках описує форму кривої зростання.
Ключові класи складності:
- O(1) — постійна: вартість не зростає. Приклад: пошук значення за індексом у масиві. Чи у масиві 10 елементів чи 10 мільйонів, один пошук залишається одним пошуком.
- O(N) — лінійна: вартість зростає зі входом. Приклад: читання кожного елемента списку один раз. Подвойте список, подвойте читання.
- O(N²) — квадратична: вартість зростає як квадрат входу. Приклад: порівняння кожного елемента з кожним іншим елементом. Подвойте N, учетверітеся робота.
Таблиця порівняння темпів зростання:
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10 000 |
| 1 000 | 1 | 1 000 | 1 000 000 |
При N=10 різниця виглядає малою. При N=1 000 розрив стає величезним.
Порівняйте O(N) та O(N²)
Використовуйте таблицю порівняння темпів зростання вище.
При N=1 000: O(N) вимагає 1 000 операцій. O(N²) вимагає 1 000 000 операцій.
Як структура коду розкриває складність
Як визначити Big O з коду
Big O приховується в формі вашого коду. Чотири закономірності охоплюють більшість випадків:
Одиничний цикл над N елементів: O(N)
# O(N): один прохід через список
for item in list_of_n_items:
process(item)Вкладені цикли, кожен над N елементів: O(N²)
# O(N²): кожен елемент спарований з кожним іншим елементом
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Пошук за постійний час: O(1)
Доступ до індексу масиву, пошук у хеш-таблиці — один крок незалежно від розміру.
Розділяй і вторюй (скорочуй задачу навпіл на кожному кроці): O(log N)
Бінарний пошук: кожна перевірка скорочує залишилися елементи.
---
Приховане O(N²): список у циклі
# Це виглядає як O(N) але це насправді O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # скануватися весь visited: O(N)
visited.append(item) # весь цикл: O(N²)Рядок if item not in visited скануватися кожен елемент visited на кожній ітерації. Сканування списку коштує O(N). Цикл який запускається N разів, кожен роблячи O(N) роботи: O(N) × O(N) = O(N²).
Це Комбінація з'являється в 1 000+ проектів з відкритим кодом. Виправлення займає один символ: замініть visited = [] на visited = set(). Перевірка приналежності набору коштує O(1), не O(N). Одна зміна. Такі ж результати. В 1 000 разів швидше при N=1 000.
Класифікуйте й виправте цей код
Прочитайте цей код:
result = []
for name in student_names:
if name not in result:
result.append(name)Теорія зустрічає практику
Big O в дикій природі
Big O не просто теорія. Вона відокремлює програми які закінчуються за секунди від програм які займають 17 хвилин — на тому ж завданні.
Реальний приклад: виявлення циклу залежності в системі побудови.
Коли ви встановлюєте програмне забезпечення, ваш комп'ютер розв'язує граф залежностей: пакет A потребує B, B потребує C, й так далі. Система побудови перевіряє цей граф на цикли.
Алгоритм виявлення циклу O(N²) працює добре при N=100 пакетів. При N=50 000 пакетів (реальний проект): це займає 17 хвилин. Виправлення O(N): 10 секунд.
Цей точний дефект існує в GHC (компілятор Haskell), pip (менеджер пакетів Python), Maven (система побудови Java), Cargo (менеджер пакетів Rust), & 1 000+ інших проектів.
Не тому що їх автори були необережні. visited = [] було написано коли N був малим. Код закристалізувався. N виріс. Ніхто не помітив доки побудова не займала пів години.
Big O це словник який дозволяє вам назвати що сталося — & виправити це.
---
Хочете заглибитися далі? Наш курс unhamming включає повну главу про Big O, MOAD-0001 (реальний дефект O(N²) знайдений в 1 000+ проектів з відкритим кодом), & чому назвати закономірність дозволяє вам знайти її везде. Див. Відсутня глава: складність алгоритмів.
Передбачте часи побудови
Система побудови використовує виявлення циклу O(N²).
Виміряні часи побудови:
- N=100 пакетів: 0,01 секунди
- N=1 000 пакетів: 1 секунда
Для O(N²): час масштабується як (N_new / N_old)².
Для O(N): час масштабується як (N_new / N_old).