Модул 26

Сложност на алгоритмите и нотация O

Какво означава един алгоритъм да е „по-бърз“ от друг, когато секундите зависят от компютъра: броене на операции, нотацията O и основните класове O(1), O(log n), O(n), O(n log n) и O(n²). Разглеждат се вложени цикли, двоично търсене, измерване със `Stopwatch`, пространствена сложност и практични правила кой подход е приемлив за какво `n`.

Част от учебната програма

Теория

Представете си две програми, които решават една и съща задача — например проверяват дали в списък с оценки има повторение. Едната приключва за миг, другата „виси“ с минути, щом списъкът стане голям. Разликата не е в компютъра, а в алгоритъма: в това колко работа върши той, когато входът расте. Сложност на алгоритъма (algorithmic complexity) наричаме зависимостта между размера на входа — бележим го с n (брой елементи в масива, символи в низа, редове в таблицата) — и количеството работа, което алгоритъмът извършва. Секундите са лош измерител, защото зависят от процесора, от другите програми и от режима на компилация, затова първо броим операции — присвоявания, сравнения, достъп до елемент — и чак после мерим време.

Да преброим операциите в прост цикъл: for (int i = 0; i < n; i++) sum += arr[i];. Тялото се изпълнява n пъти и при всяко завъртане има сравнение i < n, увеличение i++ и събиране — около 3n операции плюс две за инициализацията, общо 3n + 2. Ако удвоим n, работата също се удвоява; множителят 3 и добавката 2 не променят това. Нотацията O (Big O notation) записва точно тази идея: запазваме само най-бързо растящия член и изхвърляме константите, затова 3n + 2 е O(n) — линейна сложност. Константите отпадат, защото зависят от езика, компилатора и машината, а не от алгоритъма, и при голямо n ролята им е незначителна в сравнение с растежа. Операции, чийто брой изобщо не зависи от n — достъп arr[i], аритметика, list.Count — са O(1), константна сложност.

Два вложени цикъла, всеки до n, изпълняват тялото n * n пъти — сложност O(n²), квадратична. Дори вътрешният цикъл да започва от i + 1 (проверка на всички двойки без повторение), броят е n(n - 1) / 2, което след изхвърляне на константата и по-малкия член пак е O(n²). Практическото следствие е брутално: при удвояване на n времето става четири пъти по-голямо, а при n = 100 000 имаме 10 милиарда операции. Правилото за комбиниране е просто — вложени цикли се умножават, последователни цикли се събират, а от сбора остава само най-големият член: O(n²) + O(n) е O(n²). Ако вътрешният цикъл върви до друга граница m, сложността е O(n * m).

Има и обратният ефект: алгоритми, които на всяка стъпка намаляват задачата наполовина. Двоичното търсене (binary search) в сортиран масив сравнява търсената стойност със средния елемент и отхвърля половината масив — после отново, и отново. От n елемента след една стъпка остават n / 2, след две n / 4, а до един елемент се стига за около log₂ n стъпки: при 1000 елемента са 10, при милион — 20, при милиард — 30. Това е O(log n), логаритмична сложност, и тя е почти толкова добра, колкото константната. Условието е масивът да е сортиран, иначе сравнението със средата не казва нищо. Когато логаритмична стъпка се повтаря за всеки от n елемента, получаваме O(n log n) — това е сложността на добрите сортиращи алгоритми, включително на Array.Sort и List<T>.Sort в .NET.

Подредени от най-добра към най-лоша, основните класове са O(1), O(log n), O(n), O(n log n), O(n²), O(n³) и O(2ⁿ). Разликите не са козметични: за n = 1 000 000 линейният алгоритъм прави милион стъпки, квадратичният — трилион, а при около 10⁸ прости операции в секунда това са съответно част от секундата и няколко часа. Важно уточнение: когато казваме, че линейното търсене е O(n), имаме предвид най-лошия случай (worst case) — елементът е последен или липсва; в най-добрия случай той е първи и търсенето приключва за O(1). Освен ако не е казано друго, нотацията O описва именно най-лошия случай, защото той е гаранцията, с която можем да планираме. И едно предупреждение в обратната посока: за много малки n константите все пак имат значение и O(n²) алгоритъм с просто тяло може да е по-бърз от „по-добър“ O(n log n) с тежка подготовка.

Теорията се проверява с измерване. Класът Stopwatch от System.Diagnostics е хронометър: Stopwatch.StartNew() го създава и пуска, Stop() го спира, а ElapsedMilliseconds (или по-точното Elapsed.TotalMilliseconds) връща изтеклото време. Измервайте само алгоритъма — без Console.WriteLine вътре в измервания участък, защото печатането е стотици пъти по-бавно от аритметиката. Пускайте програмата в режим Release (dotnet run -c Release), извикайте измервания метод няколко десетки пъти върху малък вход (JIT компилаторът в .NET оптимизира метод едва след около 30 извиквания), и чак тогава мерете; повтаряйте измерването, защото едно единствено число е шум. Най-полезният експеримент е тестът с удвояване: пуснете алгоритъма с n, 2n, 4n, 8n и погледнете множителя — около 2 означава O(n), около 4 — O(n²), почти без промяна — O(log n) или O(1).

Освен време алгоритъмът харчи и памет. Пространствената сложност (space complexity) брои допълнителната памет като функция на n, без самия вход: алгоритъм, който работи с няколко променливи, е O(1) по памет, HashSet<int> с всички елементи е O(n), а таблица n × n е O(n²). Често двете се разменят: проверката за дубликати с два вложени цикъла е O(n²) време и O(1) памет, а с HashSet — O(n) време срещу O(n) памет, и обикновено паметта е по-евтината жертва. Няколко практични ориентира: до n ≈ 1000 квадратичен алгоритъм е напълно приемлив, до n ≈ 100 000 вече трябва O(n log n), а при милиони елементи — O(n) или O(n log n) без изключение. Избирайте структурата от данни според операциите, които ще правите най-често (List<T> за достъп по индекс, HashSet<T> и Dictionary<K,V> за търсене, Queue<T> за опашка), и помнете реда: първо работещ код, после измерване, чак тогава оптимизация на доказано бавното място.

Златни правила

Броим операции, не секунди

Времето зависи от процесора, от режима на компилация и от това какво друго върви на компютъра. Броят операции като функция на n зависи само от алгоритъма — затова сложността се определя първо на хартия и чак после се проверява с хронометър.

Вложените цикли се умножават, последователните се събират

Цикъл до n вътре в цикъл до n дава n² изпълнения на тялото; два отделни цикъла един след друг дават 2n. От сбора остава само най-големият член: O(n²) + O(n) = O(n²).

Константите падат, най-големият член остава

3n + 2, n / 2 и 100n са все O(n); n² / 2 + 5n е O(n²). Нотацията O описва как расте работата, а не точния брой операции, затова множителите и по-малките членове не се пишат.

Половината на всяка стъпка означава `O(log n)`

Щом всяка стъпка отхвърля половината от оставащата задача, стъпките са около log₂ n — 20 за милион елемента. Двоичното търсене работи само върху сортирани данни; върху несортирани връща грешен отговор, не просто по-бавно.

Измервай в Release, с голямо `n` и повече от веднъж

Debug режимът, JIT загрявката и Console.WriteLine в измервания участък изкривяват резултата десетки пъти. Удвоявайте n и гледайте множителя — той казва класа на сложност по-честно от едно единствено число в милисекунди.

Бърз справочник

Класове на сложност

Нотация и имеТипичен кодОперации при n = 1000Ако n се удвои
O(1) константнаarr[i], dict[key], аритметика1без промяна
O(log n) логаритмичнадвоично търсене, деление на n наполовина в цикъл≈ 10+1 стъпка
O(n) линейнаедин цикъл до n, list.Contains, сума на масив1 000×2
O(n log n) линейно-логаритмичнаArray.Sort, сортиране чрез сливане≈ 10 000малко над ×2
O(n²) квадратичнадва вложени цикъла, bubble sort, Contains в цикъл1 000 000×4
O(n³) кубичнатри вложени цикъла, умножение на матрици1 000 000 000×8
O(2ⁿ) експоненциалнавсички подмножества, наивно рекурсивно Фибоначи≈ 10³⁰¹×2 при всяко n + 1

Сложност на често използвани операции в .NET

ОперацияСложностЗащоПо-добра алтернатива
arr[i], list[i]O(1)индексът е директен адрес в паметта—
list.Add(x)O(1) амортизиранорядко вътрешният масив се копира в двойно по-голямзадайте капацитет: new List<int>(n)
list.Contains(x), Array.IndexOfO(n)обхожда елементите подредHashSet<T>.Contains — O(1)
list.Insert(0, x), list.RemoveAt(0)O(n)измества всички останали елементиQueue<T>.Dequeue() вместо RemoveAt(0); LinkedList<T>.AddFirst вместо Insert(0, x) — и двете O(1)
dict[key], set.Add(x), set.Contains(x)O(1) среднохеш-таблица: ключът сочи мястото направо—
Array.Sort, list.Sort()O(n log n)introsort — комбинация от quicksort, heapsort и insertion sortсортирайте веднъж, не във всеки цикъл
Array.BinarySearch(arr, x)O(log n)половинява интервала; само за сортиран масив—
s1 + s2, s += xO(дължина)низовете са неизменими: създава се нов и се копираStringBuilder.Append — O(1) амортизирано
queue.Dequeue(), stack.Pop()O(1)Pop взема последния, Dequeue — първия елемент; и двете без изместване на останалите—

Код за анализ и пренаписване

Броене на стъпки: линейно срещу двоично търсене

Program.cs
using System;

class Program
{
    static int steps;

    static int LinearSearch(int[] arr, int target)
    {
        steps = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            steps++;
            if (arr[i] == target)
            {
                return i;
            }
        }
        return -1;
    }

    static int BinarySearch(int[] arr, int target)
    {
        steps = 0;
        int left = 0;
        int right = arr.Length - 1;
        while (left <= right)
        {
            steps++;
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
            {
                return mid;
            }
            if (arr[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return -1;
    }

    static void Main()
    {
        int[] sizes = { 10, 1000, 1_000_000 };
        foreach (int n in sizes)
        {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
            {
                arr[i] = i * 2;          // сортиран масив: 0, 2, 4, 6, ...
            }
            int target = arr[n - 1];     // най-лошият случай: последният елемент

            LinearSearch(arr, target);
            int linearSteps = steps;
            BinarySearch(arr, target);
            int binarySteps = steps;

            Console.WriteLine($"n = {n,9}: линейно = {linearSteps,9} стъпки, двоично = {binarySteps,3} стъпки");
        }
    }
}

Какво се случва тук?

  • Статичната променлива steps брои колко пъти се изпълнява тялото на цикъла — това е нашият „брояч на операции“, който не зависи от скоростта на компютъра.
  • LinearSearch проверява елементите подред; търсим последния елемент arr[n - 1], което е най-лошият случай, затова броячът показва точно n стъпки — O(n).
  • BinarySearch поддържа интервал [left, right], изчислява средата mid и според сравнението отхвърля лявата или дясната половина; записът left + (right - left) / 2 е по-безопасен от (left + right) / 2, защото не препълва int при много големи индекси.
  • Масивът се пълни с i * 2, така че е сортиран — задължително условие за двоичното търсене; при несортиран масив методът би връщал -1 за стойности, които всъщност ги има.
  • Изходът показва 10, 1000 и 1 000 000 стъпки за линейното търсене срещу 4, 10 и 20 за двоичното: всяко увеличаване на n хиляда пъти добавя само около 10 стъпки на логаритмичния алгоритъм.
  • Форматът {n,9} в интерполирания низ подравнява числата вдясно в поле от 9 символа, така че резултатът се чете като таблица.
  • Опитайте да търсите стойност, която я няма (например -5 или нечетно число): линейното търсене пак прави n стъпки, а двоичното — най-много log₂ n + 1.

Тест с удвояване със Stopwatch

Program.cs
using System;
using System.Diagnostics;

class Program
{
    // O(n): едно обхождане на масива
    static long SumAll(int[] arr)
    {
        long sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            sum += arr[i];
        }
        return sum;
    }

    // O(n^2): събираме произведенията на всички двойки (i, j) с i < j
    static long SumPairs(int[] arr)
    {
        long total = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = i + 1; j < arr.Length; j++)
            {
                total += arr[i] * arr[j];
            }
        }
        return total;
    }

    static int[] RandomArray(int n)
    {
        var rnd = new Random(7);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = rnd.Next(1000);
        }
        return arr;
    }

    static void Main()
    {
        // Загрявка: JIT оптимизира метод едва след около 30 извиквания,
        // затова викаме двата метода 50 пъти върху малък масив, преди да мерим
        int[] warm = RandomArray(2000);
        for (int i = 0; i < 50; i++)
        {
            SumAll(warm);
            SumPairs(warm);
        }

        Console.WriteLine("Линеен алгоритъм (n се удвоява):");
        for (int n = 2_000_000; n <= 16_000_000; n *= 2)
        {
            int[] arr = RandomArray(n);
            long sum = 0;
            double best = double.MaxValue;
            for (int run = 0; run < 3; run++)       // мерим три пъти, пазим най-доброто
            {
                Stopwatch sw = Stopwatch.StartNew();
                sum = SumAll(arr);
                sw.Stop();
                best = Math.Min(best, sw.Elapsed.TotalMilliseconds);
            }
            Console.WriteLine($"  n = {n,10}: {best,8:F2} ms (сума {sum})");
        }

        Console.WriteLine("Квадратичен алгоритъм (n се удвоява):");
        for (int n = 2_000; n <= 32_000; n *= 2)
        {
            int[] arr = RandomArray(n);
            long pairs = 0;
            double best = double.MaxValue;
            for (int run = 0; run < 3; run++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                pairs = SumPairs(arr);
                sw.Stop();
                best = Math.Min(best, sw.Elapsed.TotalMilliseconds);
            }
            Console.WriteLine($"  n = {n,10}: {best,8:F2} ms (сума на двойките {pairs})");
        }
    }
}

Какво се случва тук?

  • SumAll обхожда масива веднъж — O(n); SumPairs обработва всяка двойка (i, j) с i < j, тоест около n² / 2 умножения и събирания — O(n²). Тялото на вътрешния цикъл нарочно няма if: при условие, което зависи от данните, процесорът „научава“ малките масиви и множителите излизат изкривени.
  • Преди измерването извикваме двата метода 50 пъти върху масив от 2000 елемента — това е загрявка: JIT компилаторът в .NET първо превежда метода в бърз, но неоптимизиран код и го оптимизира едва след около 30 извиквания, така че едно единствено извикване не стига и първите редове биха излезли по-бавни от истинското време.
  • Stopwatch.StartNew() пуска хронометъра непосредствено преди извикването, а Stop() го спира веднага след него; между тях няма Console.WriteLine, защото печатането би било по-бавно от самата сметка.
  • Резултатите sum и pairs се отпечатват нарочно — ако стойността не се използва никъде, оптимизаторът може да премахне част от изчислението и да измерим почти нула.
  • Всяко n се измерва три пъти и се пази най-малкото време с Math.Min, защото случайните смущения от други програми само добавят време. В линейната серия n се удвоява от 2 до 16 милиона и времето расте почти точно 2 пъти на ред; в квадратичната n расте от 2000 до 32 000 и множителят е около 4 — например 0.57, 2.24, 8.85, 35.3 и 141 ms.
  • Абсолютните милисекунди на вашия компютър ще са различни — важни са множителите между редовете, защото те издават класа на сложност; пускайте с dotnet run -c Release, за да не измервате Debug код.
  • Форматът {best,8:F2} подравнява времето в поле от 8 символа с две цифри след десетичния знак; ElapsedMilliseconds би върнал цяло число и би показал 0 за най-бързите измервания.

Внимавай! Чести грешки

Грешките, които почти всеки прави в тази тема — виж разликата между грешния и правилния код.

`Contains` на `List` вътре в цикъл

Грешно

var seen = new List<int>();
foreach (int x in numbers)
{
    if (!seen.Contains(x))   // Contains обхожда целия списък: O(n)
    {
        seen.Add(x);
    }
}

Правилно

var seen = new HashSet<int>();
foreach (int x in numbers)
{
    seen.Add(x);             // проверява и добавя за O(1) средно
}

List<T>.Contains обхожда списъка елемент по елемент — O(n); извикан за всеки от n елемента, дава O(n²). HashSet<T>.Add сам проверява дали стойността вече я има и работи за O(1) средно, така че целият цикъл става O(n).

Слепване на низ с `+=` в цикъл

Грешно

string result = "";
for (int i = 0; i < n; i++)
{
    result += i + ",";       // всеки път се копира целият досегашен низ
}

Правилно

var sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
    sb.Append(i).Append(',');
}
string result = sb.ToString();

Низовете в C# са неизменими: всяко += създава нов низ и копира всичко досега, което за n стъпки е O(n²) копирани символа. StringBuilder (от System.Text) добавя в разширяем буфер за O(1) амортизирано и създава крайния низ само веднъж с ToString().

Измерване, в което влиза и печатането

Грешно

var sw = Stopwatch.StartNew();
for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine(arr[i]);   // печатането е по-бавно от самата работа
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

Правилно

long sum = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < arr.Length; i++)
{
    sum += arr[i];
}
sw.Stop();
Console.WriteLine($"{sum} за {sw.ElapsedMilliseconds} ms");

Console.WriteLine е стотици пъти по-бавно от едно събиране, така че хронометърът мери конзолата, а не алгоритъма. Измервайте само изчислението, печатайте резултата след Stop() и пускайте в Release режим с достатъчно голямо n.

`RemoveAt(0)` в цикъл вместо опашка

Грешно

while (list.Count > 0)
{
    int first = list[0];
    list.RemoveAt(0);        // измества всички останали елементи: O(n)
    Process(first);
}

Правилно

var queue = new Queue<int>(list);
while (queue.Count > 0)
{
    int first = queue.Dequeue();   // O(1)
    Process(first);
}

Премахването на първия елемент от List<T> измества всички останали наляво — O(n) всеки път, O(n²) за целия цикъл. Queue<T> е направена точно за „първи влязъл, първи излязъл“ и Dequeue() е O(1).

Задачи за самостоятелна работа

Опитай първо сам — подсказката е там само ако наистина закъсаш.

Брояч на операции

Напишете програма с три метода, всеки от които връща колко пъти се е изпълнило тялото на цикъла му: CountLinear(n) с един цикъл до n, CountQuadratic(n) с два вложени цикъла до n и CountLogarithmic(n) с цикъл, който дели n на 2, докато стане 1. Извикайте ги за n = 10, 100, 1000, 10000 и отпечатайте резултатите като таблица. Какъв е множителят във всяка колона, когато n расте 10 пъти?

Хиляда търсения

Създайте сортиран масив от 1 000 000 числа (arr[i] = i * 3) и 1000 случайни търсени стойности от интервала [0, 3 000 000). Пребройте колко от тях присъстват в масива по два начина: с ваше линейно търсене и с вградения метод Array.BinarySearch. Измерете общото време на всеки подход със Stopwatch и обяснете разликата с нотация O.

Двойка със зададена сума

Дадени са масив от цели числа и число target. Напишете две версии на метод, който проверява дали има два различни елемента със сума target: HasPairSlow с два вложени цикъла и HasPairFast с HashSet<int>, който за всеки елемент x проверява дали вече е срещал target - x. Измерете двете версии за n = 10 000, 20 000, 40 000 в най-лошия случай (масив само от четни числа и нечетно target). Каква е времевата и пространствената сложност на всяка версия?

Мини-тест за проверка

Отговори си наум (или на глас!) и чак тогава разкрий отговора.

1. Каква е сложността на код, в който първо има два вложени цикъла до `n`, а след тях — отделен цикъл до `n`?

2. Защо казваме, че `5n + 100` е `O(n)`, а не `O(5n + 100)`?

3. Колко сравнения прави двоичното търсене в сортиран масив от 1 000 000 елемента в най-лошия случай и защо не работи върху несортиран масив?

4. Измервате алгоритъм със `Stopwatch`: при `n = 10 000` той работи 50 ms, при `n = 20 000` — 200 ms, при `n = 40 000` — 800 ms. Какъв е класът му на сложност?

Речник на термините

Виж пълния речник на курса
Сложност на алгоритъм (algorithmic complexity)
Зависимост между размера на входа n и ресурсите — време или памет — които алгоритъмът изразходва. Позволява алгоритмите да се сравняват независимо от конкретния компютър.
Времева сложност (time complexity)
Броят операции, които алгоритъмът извършва като функция на n. Записва се с нотация O, например O(n log n).
Пространствена сложност (space complexity)
Допълнителната памет, която алгоритъмът използва освен самия вход, като функция на n. Няколко променливи са O(1), копие на масива — O(n).
Нотация O (Big O notation)
Запис на класа на нарастване, в който се запазва само най-бързо растящият член и се изхвърлят константите: 3n² + 10n е O(n²).
Най-лош случай (worst case)
Входът, при който алгоритъмът върши най-много работа, например липсващ елемент при линейно търсене. Нотацията O по подразбиране описва именно него.
Двоично търсене (binary search)
Търсене в сортиран масив, което на всяка стъпка сравнява със средния елемент и отхвърля половината; работи за O(log n).
Логаритъм (logarithm, log₂ n)
Колко пъти трябва да разделим n на 2, за да стигнем до 1: log₂ 1024 = 10, log₂ 1 000 000 ≈ 20.
Амортизирана сложност (amortized complexity)
Средна цена на една операция в дълга поредица, когато повечето са евтини, а рядко някоя е скъпа. List<T>.Add е O(1) амортизирано, макар понякога да копира целия вътрешен масив.
Stopwatch
Клас от System.Diagnostics за точно измерване на време: StartNew(), Stop(), Restart(), ElapsedMilliseconds, Elapsed.TotalMilliseconds.

Провери знанията

Бърз тест с избор от отговори върху термините на модула — с точки и моментална обратна връзка.

Провери знанията си

9 въпроса върху термините от модула. Показваме определение — ти избираш правилния термин.

Препоръки за този модул

  • Преди да напишете решение, запишете колко голямо може да бъде n в реалната задача. Ориентир: около 10⁸ прости операции в секунда — ако n² надхвърля това число, квадратичният подход е изключен още на хартия.
  • За всеки цикъл в кода си задавайте въпроса „колко пъти се изпълнява това тяло като функция на n?“ и пишете отговора като коментар над цикъла. След няколко седмици ще определяте сложността с един поглед.
  • Правете теста с удвояване със Stopwatch: n, 2n, 4n, 8n. Запишете времената в таблица и сметнете множителите — ако не са близо до 2 или 4, най-вероятно измервате грешно (Debug режим, твърде малко n, печатане в цикъла).
  • Научете наизуст сложността на операциите на колекциите, които ползвате всеки ден: List<T>.Contains е O(n), HashSet<T>.Contains е O(1), RemoveAt(0) е O(n). В повечето ученически програми цялата „оптимизация“ е смяна на колекцията.

Учебен наръчник — теория, примери, задачи и тестове по предметите от учебния план.

Натисни Ctrl K или / отвсякъде, за да търсиш.