Big-O нотация и сложност на алгоритмите в Python

Проблем

Ще издържи ли при милион?

Магазинът подписа договор с голям доставчик. След месец каталогът става от 1 000 на 1 000 000 продукта. В кода има шест функции, през които минава всеки продукт или всяко плащане:

първата цена в списъка (за банера на началната страница);
търсене на цена в подредения ценоразпис;
сумата на цените (за отчета);
подреждане на цените (за страницата „от най-евтиното“);
проверката за двойни плащания от предишния урок;
всички комбинации от продукти, които се побират в бюджета на клиента.

Кои ще издържат? Данни с милион продукта още няма, а секундите на твоя лаптоп и без това лъжат. Трябва да познаеш от кода. Да броиш точно всяка стъпка, както с n(n − 1) / 2, е бавно. А и подробностите не са важни: важно е как расте работата.

Идеята

Big-O: какво прави удвояването

Big-O е кратко име за това как расте броят операции, когато расте n (колко са данните). Не казва секунди, а форма: какво става с работата, когато данните се удвоят.

Клас	Име	Пример от магазина	n се удвоява → работата
O(1)	константа	първата цена	не се сменя
O(log n)	логаритъм	търсене в подредения ценоразпис	една стъпка повече
O(n)	линейна	сумата на цените	×2
O(n log n)	„n лог n“	подреждане	малко над ×2
O(n²)	квадратна	двойните плащания	×4
O(2ⁿ)	експоненциална	всички комбинации в бюджета	на квадрат

Ето и шестте функции. Цените са в евроцентове, за да са цели числа:

def first_price(prices):
    return prices[0]

def total(prices):
    result = 0
    for p in prices:
        result += p
    return result

def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found

first_price прави една стъпка, колкото и цени да има. total прави по една на цена. double_payments прави по една на двойка.

Виж го

O(log n): колко пъти делиш на две

Търсенето в подредения ценоразпис гледа средата. Ако търсената цена е по-голяма, лявата половина изобщо не трябва и се изхвърля. Иначе се изхвърля дясната. Така на всяка проверка остава половината:

def index_of(ordered, price):
    lo = 0
    hi = len(ordered) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if ordered[mid] == price:
            return mid
        elif ordered[mid] < price:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Колко проверки, ако цената я няма? Колкото пъти можеш да разделиш n на две, докато не остане нищо. Това е логаритъмът: log₂ n е „колко пъти делиш на две“.

for n in [1000, 100000, 1000000, 1000000000]:
    halvings = 0
    left = n
    while left > 0:
        left //= 2
        halvings += 1
    print(n, "→", halvings)

1000 → 10
100000 → 17
1000000 → 20
1000000000 → 30

Хиляда пъти повече цени (от 1 000 на 1 000 000) е само 10 проверки повече. Удвояването добавя една. Затова O(log n) почти не расте.

Повече за границите на двоичното търсене (и къде се бърка с единица) ще видиш в урока „Двоично търсене“.

Виж го

O(n log n) и O(2ⁿ)

Подреждането ползва вградения sorted:

def sorted_prices(prices):
    return sorted(prices)

Добрите алгоритми за подреждане разделят масива на половини (log n нива) и на всяко ниво минават всичко веднъж (n стъпки). Затова са O(n log n). Как точно, ще видиш в урока за merge sort.

Комбинациите в бюджета: за всеки продукт има два избора, „взимам“ или „не взимам“. Затова combos вика себе си два пъти:

def combos(prices, i, total, budget):
    if i == len(prices):
        return 1 if total <= budget else 0
    return (combos(prices, i + 1, total, budget)
            + combos(prices, i + 1, total + prices[i], budget))

С 1 продукт комбинациите са 2, с 2 са 4, с 3 са 8. Всеки нов продукт удвоява всичко, което е имало досега. Това е O(2ⁿ).

Всичките шест, пуснати върху пет цени и пет плащания:

prices = [1299, 450, 3999, 899, 2450]
sorted_list = sorted_prices(prices)
payments = [100231, 100232, 100233, 100232, 100234]
print("Първата цена: " + str(first_price(prices)))
print("2450 е на място " + str(index_of(sorted_list, 2450)))
print("Сумата: " + str(total(prices)))
print("Най-евтина: " + str(sorted_list[0]) + ", най-скъпа: " + str(sorted_list[4]))
print("Двойни плащания: " + str(double_payments(payments)))
print("Комбинации до 5000: " + str(combos(prices, 0, 0, 5000)))

Първата цена: 1299
2450 е на място 3
Сумата: 9097
Най-евтина: 450, най-скъпа: 3999
Двойни плащания: 1
Комбинации до 5000: 18

Виж го

Какво прави удвояването

def combos(prices, i, total, budget):
    if i == len(prices):
        return 1 if total <= budget else 0
    return (combos(prices, i + 1, total, budget)
            + combos(prices, i + 1, total + prices[i], budget))

def index_of(ordered, price):
    lo = 0
    hi = len(ordered) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if ordered[mid] == price:
            return mid
        elif ordered[mid] < price:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def combos(prices, i, total, budget):
    if i == len(prices):
        return 1 if total <= budget else 0
    return (combos(prices, i + 1, total, budget)
            + combos(prices, i + 1, total + prices[i], budget))

Стъпка по стъпка, с думи

Първата цена: една стъпка при 4 цени и при 8. Работата не зависи от n: O(1).
Двоичното търсене гледа средата и изхвърля половината. 4 → 2 → 1 са 3 проверки, 8 → 4 → 2 → 1 са 4. Двойно повече цени, една проверка повече: O(log n).
Сумата минава всяка цена по веднъж: 4 и 8 стъпки. Двойно повече цени, двойно повече работа: O(n).
Подреждането слива на нива (тук merge sort, както в Bench). Нивата са log n, на всяко най-много n сравнения: 5 → 16. O(n log n).
Двойните плащания: всяко с всяко след него. 6 → 28: триъгълникът расте в две посоки. O(n²).
Комбинациите в бюджета: всеки продукт е „взимам“ или „не“, и всеки нов ги удвоява. 16 → 256: с 8 продукта работата е тази за 4, на квадрат. O(2ⁿ).

Шестте класа при 4 и при 8 цени. Всяко кубче е една стъпка, точно колкото брои Bench. O(1) не мърда. O(log n) добавя една лента. O(n) се удвоява. O(n log n) се удвоява и получава още едно ниво. O(n²) расте в две посоки. O(2ⁿ) от квадрат 4 × 4 става квадрат 16 × 16.

Идеята

Константите и малките членове падат

Отчетът за двойните плащания прави n(n − 1) / 2 = n²/2 − n/2 стъпки. Защо е O(n²), а не O(n²/2 − n/2)?

По-малкият член изчезва, когато n расте:

n	n²/2	n/2	колко е n/2 от всичко
10	50	5	10%
1 000	500 000	500	0,1%
100 000	5 000 000 000	50 000	0,001%

Константата не сменя формата. n²/2 и n² растат еднакво: двойно повече данни, четири пъти повече работа. Константата е като по-бавна машина: сменя секундите, но не и това какво става при удвояване. А секундите вече знаеш, че лъжат.

Затова Big-O пази само най-бързо растящия член, без числото пред него: 3n + 5 е O(n), n²/2 − n/2 е O(n²), 2n log n + 7n е O(n log n).

По-точно, за любопитните

Точното определение: f(n) е O(g(n)), ако има константа c и праг n₀, такива че f(n) ≤ c · g(n) за всяко n ≥ n₀. Тоест от някое n нататък f не расте по-бързо от g, с точност до константа. Затова O(n) е и O(n²) (горна граница е), но казваме най-тясната. Има и Θ (точно толкова) и Ω (поне толкова). В разговори и на интервюта „O(n)“ обикновено значи Θ(n).

Основата на логаритъма също не се пише: log₂ n и log₁₀ n се различават с константа (log₂ n ≈ 3,32 · log₁₀ n).

Виж го

Шестте криви в браузъра

Пусни шестте функции на Bench. Оста е логаритмична: всяка черта е ×10. O(n) е права линия, O(n²) е два пъти по-стръмна, а O(2ⁿ) излита веднага.

Първата цена O(1)
Двоично търсене O(log n)
Сумата на цените O(n)
Подреждане (merge sort) O(n log n)
Всяка двойка поръчки O(n²)
Всички комбинации в бюджета O(2ⁿ)

Алгоритъм	n = 10	n = 1000	n = 100 000
Първата цена	1	1	1
Двоично търсене	4	10	17
Сумата на цените	10	1000	100 000
Подреждане (merge sort)	21	8709	1 536 371
Всяка двойка поръчки	45	499 500	≈ 4 995 000 000
Всички комбинации в бюджета	1024	≈ 10³⁰¹	≈ 10³⁰¹⁰²

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Отговорът за милиона продукта: първата цена, търсенето, сумата и подреждането ще издържат. Двойните плащания стават 500 милиарда стъпки и трябва да минат към множеството от предишния урок. А всички комбинации на милион продукта не може да се изброят на никой компютър: 2 на степен милион е число с 301 030 цифри.

По-точно, за любопитните

Какво ползва вграденото подреждане на всеки език. sorted и list.sort са TimSort (от Python 3.11 с подобрено сливане, Powersort). O(n log n), а върху почти подредени данни е близо до O(n). Bench брои сравненията на merge sort, защото вграденото не може да се преброи отвън. Класът е същият.

Пробвай

Предвиди изхода

Външният цикъл минава n = 8 пъти. Вътрешният дели на две, докато не остане нищо. Какво печата програмата?

n = 8
steps = 0
for i in range(n):
    left = n
    while left > 0:
        left //= 2
        steps += 1
print(steps)

Отговор

Пробвай

Намери скрития цикъл

Функцията брои различните клиенти в поръчките на месеца. Има само един цикъл, а при 100 000 поръчки е бавна като отчета за двойните плащания:

def unique_customers(orders):
    seen = []
    for customer in orders:
        if customer not in seen:
            seen.append(customer)
    return len(seen)

orders = [7, 3, 7, 12, 3, 7]
print(unique_customers(orders))

На кой ред се крие вторият цикъл?

Избери реда с грешката.

Упражнение

Колко комбинации

Реши задачата в редактора си.

Стъпките на комбинациите. Добави брояч steps в combos: една стъпка за всяка готова комбинация (когато i стигне края). Пусни я с 10, 11 и 12 продукта с цени 500 + 100 · k цента и бюджет 5000 и изпечатай стъпките:

10 продукта: 1024 стъпки
11 продукта: 2048 стъпки
12 продукта: 4096 стъпки

Всеки продукт удвоява стъпките. Колко са при 20 продукта? А при 40? Сметни, преди да пуснеш.

Още задачи

Класът на всяка функция. Напиши Big-O на всяка от функциите от урока „Времева сложност: броене на стъпки“, включително продажбите по продукт (50 продукта × n поръчки).
Двоично търсене с брояч. Добави брояч в index_of и потърси цена, която я няма, в 1 000 и в 100 000 подредени цени. Сравни с програмата, която дели на две.
Пак множество. Поправи броенето на различните клиенти с множество и сравни стъпките при 1 000 различни клиенти.

Тест

Провери се

1. Функция прави 3n + 5 стъпки. Каква е сложността ѝ?O(1)O(3n + 5)O(n)

2. Алгоритъм е O(n²). Данните стават 10 пъти повече. Колко пъти повече работа да очакваш?10 пътиОколо 20 пътиОколо 100 пъти

3. Колко проверки прави двоичното търсене в подреден списък от 1 000 000 цени, когато цената я няма?Около 1 000Около 20Около 500 000

4. Комбинациите в бюджета са O(2ⁿ). Колко са при 30 продукта?Над милиардОколо 90060

5. Два алгоритъма за едно и също: единият е O(n log n), другият е O(n²). При 10 елемента вторият е по-бърз. Кой избираш за 1 000 000 поръчки?Все едноO(n log n): при голямо n кривата решава, а не константитеO(n²), щом е по-бърз

Big-O: как расте работата

Бисквитки