Теория
Представете си две програми, които решават една и съща задача — например проверяват дали в списък с оценки има повторение. Едната приключва за миг, другата „виси“ с минути, щом списъкът стане голям. Разликата не е в компютъра, а в алгоритъма: в това колко работа върши той, когато входът расте. Сложност на алгоритъма (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.IndexOf | O(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 += x | O(дължина) | низовете са неизменими: създава се нов и се копира | StringBuilder.Append — O(1) амортизирано |
queue.Dequeue(), stack.Pop() | O(1) | Pop взема последния, Dequeue — първия елемент; и двете без изместване на останалите | — |
Код за анализ и пренаписване
Броене на стъпки: линейно срещу двоично търсене
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
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. Какъв е класът му на сложност?
Речник на термините
Виж пълния речник на курсаn и ресурсите — време или памет — които алгоритъмът изразходва. Позволява алгоритмите да се сравняват независимо от конкретния компютър.n. Записва се с нотация O, например O(n log n).n. Няколко променливи са O(1), копие на масива — O(n).3n² + 10n е O(n²).O(log n).n на 2, за да стигнем до 1: log₂ 1024 = 10, log₂ 1 000 000 ≈ 20.List<T>.Add е O(1) амортизирано, макар понякога да копира целия вътрешен масив.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). В повечето ученически програми цялата „оптимизация“ е смяна на колекцията.