AcademyCloud — онлайн-курси програмування

Більшість програмістів пише робочий код, не думаючи про складність. Це нормально — доки даних мало. Проблема в тому, що момент, коли їх стає багато, настає раптово: вчора все літало на тисячі записів, сьогодні на мільйоні впало.

Навіщо це насправді

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

Кількість операцій при n = 1 000 000

O(1)        1
O(log n)    20
O(n)        1 000 000
O(n log n)  20 000 000
O(n²)       1 000 000 000 000     ← близько 11 днів

Різниця між O(n log n) і O(n²) — не «трохи повільніше». Це різниця між секундою й тижнем.

O-нотація

O(f(n)) описує, як росте кількість операцій зі зростанням n. Дві умови, які роблять її корисною:

Константи відкидаються. O(2n) це O(n), O(n/2) теж O(n). Нас цікавить форма зростання, а не множник.

Лишається старший член. O(n² + n) це O(n²), бо при великому n доданок n не має значення.

Як рахувати

Послідовні дії — беремо більшу:

for x in arr:      # O(n)
    print(x)
for x in arr:      # O(n)
    print(x)
# Разом: O(n) + O(n) = O(2n) = O(n)

Вкладені цикли — множимо:

for i in arr:          # n
    for j in arr:      # n
        print(i, j)
# O(n²)

Ділення навпіл — логарифм:

while n > 1:
    n = n // 2
# O(log n) — щоб дійти від мільйона до 1, треба 20 кроків

Цикл із діленням усередині:

for i in range(n):        # n
    x = n
    while x > 1:          # log n
        x //= 2
# O(n log n)

Пастка: приховані цикли

Найпоширеніша помилка — не побачити складність у виклику бібліотечної функції.

# Виглядає як один цикл — насправді O(n²)
result = []
for x in items:
    if x not in result:      # ← пошук у списку це O(n)
        result.append(x)

x not in result для списку — повний перебір. Разом виходить O(n²).

# O(n)
seen = set()
result = []
for x in items:
    if x not in seen:        # ← у множині це O(1)
        seen.add(x)
        result.append(x)

Той самий результат, різниця на порядки.

Інші приховані витрати, про які варто пам'ятати:

Операція	Складність
`list.insert(0, x)`	O(n) — зсув усіх елементів
`list.pop(0)`	O(n)
`x in list`	O(n)
`x in set` / `x in dict`	O(1)
`list[i]`	O(1)
конкатенація рядків у циклі	O(n²)
`sorted(arr)`	O(n log n)

Три випадки

def find(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

Найкращий: O(1) — елемент перший
Середній: O(n)
Найгірший: O(n) — елемента немає

За замовчуванням говорять про найгірший: він дає гарантію, а не сподівання.

Окремий випадок — амортизована складність. list.append зазвичай O(1), але іноді масив розширюється з копіюванням за O(n). Усереднено на багато операцій виходить O(1) — це й називають амортизованим.

Пам'ять

Складність буває не лише за часом:

# O(1) додаткової пам'яті
def total(arr):
    s = 0
    for x in arr:
        s += x
    return s

# O(n) додаткової пам'яті
def doubled(arr):
    return [x * 2 for x in arr]

Часто доводиться обирати: швидше, але з додатковою пам'яттю, чи повільніше, але на місці. Хеш-таблиця — класичний приклад обміну пам'яті на час.

Практична перевірка

Теорію завжди корисно звірити з годинником:

import time

def measure(fn, n):
    data = list(range(n))
    start = time.perf_counter()
    fn(data)
    return time.perf_counter() - start

for n in [1000, 2000, 4000, 8000]:
    print(n, round(measure(my_function, n), 4))

Дивись, як росте час при подвоєнні n:

час не змінився → O(1) або O(log n)
подвоївся → O(n)
зріс трохи більше ніж удвічі → O(n log n)
зріс учетверо → O(n²)

Це найнадійніший спосіб перевірити свою оцінку.

Коли на це можна не зважати

Чесно: якщо n завжди менше сотні, різниці немає. O(n²) на 50 елементах — 2500 операцій, тобто миттєво.

Складність важлива там, де:

дані ростуть із часом (таблиця в базі, лог, список користувачів)
код виконується в циклі, який сам залежить від n
це запит, що обробляє введення ззовні

Не оптимізуй наперед. Але вмій розпізнати O(n²) там, де n колись стане великим.

Практика

Оціни складність трьох функцій із власного коду.
Знайди в коді x in list усередині циклу й заміни на set.
Заміряй час для n = 1000, 2000, 4000, 8000 і визнач складність за приростом.
Напиши дві версії пошуку дублікатів: O(n²) і O(n). Порівняй на 50 000 елементів.

Підсумок

O-нотація описує зростання, константи й молодші члени відкидаються
Послідовні дії — максимум, вкладені — добуток, ділення навпіл — логарифм
x in list це O(n), x in set це O(1) — джерело більшості прихованих O(n²)
За замовчуванням оцінюють найгірший випадок
Пам'ять — теж ресурс; хеш-таблиця міняє її на час
Перевіряй оцінку годинником: подвоїв n, подивись на приріст

Далі — масиви й техніка двох вказівників.

Складність: O-нотація на практиці