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

Проблем

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

Магазинът подписа договор с голям доставчик. След месец каталогът става от 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ⁿ)	експоненциална	всички комбинации в бюджета	на квадрат

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

static int FirstPrice(int[] prices)
{
    return prices[0];
}

static int Total(int[] prices)
{
    int sum = 0;
    foreach (int p in prices)
    {
        sum += p;
    }
    return sum;
}

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

FirstPrice прави една стъпка, колкото и цени да има. Total прави по една на цена. DoublePayments прави по една на двойка.

Виж го

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

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

static int IndexOf(int[] sorted, int price)
{
    int lo = 0;
    int hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (sorted[mid] == price)
        {
            return mid;
        }
        else if (sorted[mid] < price)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

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

foreach (int n in new[] { 1000, 100000, 1000000, 1000000000 })
{
    int halvings = 0;
    for (int left = n; left > 0; left /= 2)
    {
        halvings++;
    }
    Console.WriteLine(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ⁿ)

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

static int[] SortedPrices(int[] prices)
{
    int[] copy = (int[])prices.Clone();
    Array.Sort(copy);
    return copy;
}

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

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

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + prices[i], budget);
}

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

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

int[] prices = { 1299, 450, 3999, 899, 2450 };
int[] sorted = SortedPrices(prices);
int[] payments = { 100231, 100232, 100233, 100232, 100234 };
Console.WriteLine("Първата цена: " + FirstPrice(prices));
Console.WriteLine("2450 е на място " + IndexOf(sorted, 2450));
Console.WriteLine("Сумата: " + Total(prices));
Console.WriteLine("Най-евтина: " + sorted[0] + ", най-скъпа: " + sorted[4]);
Console.WriteLine("Двойни плащания: " + DoublePayments(payments));
Console.WriteLine("Комбинации до 5000: " + Combos(prices, 0, 0, 5000));

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

Виж го

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

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + prices[i], budget);
}

static int IndexOf(int[] sorted, int price)
{
    int lo = 0;
    int hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (sorted[mid] == price)
        {
            return mid;
        }
        else if (sorted[mid] < price)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + 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 цифри.

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

Какво ползва вграденото подреждане на всеки език. Array.Sort е introsort: quick sort, който минава към heap sort, ако рекурсията стане твърде дълбока, и към insertion sort за малки части. O(n log n) в най-лошия случай. Bench брои сравненията на merge sort, защото вграденото не може да се преброи отвън. Класът е същият.

Пробвай

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

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

int n = 8;
int steps = 0;
for (int i = 0; i < n; i++)
{
    for (int left = n; left > 0; left /= 2)
    {
        steps++;
    }
}
Console.WriteLine(steps);

Отговор

Пробвай

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

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

static int UniqueCustomers(int[] orders)
{
    var seen = new List<int>();
    foreach (int customer in orders)
    {
        if (!seen.Contains(customer))
        {
            seen.Add(customer);
        }
    }
    return seen.Count;
}

int[] orders = { 7, 3, 7, 12, 3, 7 };
Console.WriteLine(UniqueCustomers(orders));

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

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

Упражнение

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

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

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

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

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

Още задачи

Класът на всяка функция. Напиши Big-O на всяка от функциите от урока „Времева сложност: броене на стъпки“, включително продажбите по продукт (50 продукта × n поръчки).
Двоично търсене с брояч. Добави брояч в IndexOf и потърси цена, която я няма, в 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: как расте работата

Бисквитки