Алгоритми/Математичке основе

Пре него што почнемо да се бавимо алгоритамским техникама, морамо да изучимо неопходне математичке основе (математички апарат). Прво ћемо да покријемо математичке дефиниције термина који се користе у књизи. Проширењем математичког вокабулара, бићете много прецизнији и у стању да много једноставније формулишете проблем. Затим ћемо обрадити технике анализе времена извршења алгоритма. После сваког битног алгоритма који је обрађен у књизи, следи анализа времена извршења и доказ исправности.

Асимптотска нотација

Уз исправност, важна одлика корисног алгоритма је време извршења и утрошени меморијски простор. Време и меморија су важни ресурси и међу њима постоји битна разлика у начину коришћења, чак и ако их има у изобиљу. Како се може измерити потрошња ресурса? Један начин је да направите функцију која одражава њихово употребу у односу на неке карактеристике улаза. Једна од уобичајених карактеристика улаза је величина скупа података. На пример, претпоставимо да је улаз неког алгоритма вектор од $n$ целих бројева. Време извршења алгортма можемо да опишемо функцијом $f$ која зависи од $n$.

$f(n)=n^{2}+3n+14$

где је вредност функције $f(n)$ изражена у некој јединици времена. (У овом разматрању главни фокус је на времену, али исто може да се примени и на утрошак меморије). Ретко се као јединица времена користи секунда, јер време извршења зависи од машине, њеног оперативног система и тренутног оптерећења. Уместо у секундама, време се најчешће изражава као потребан број неких основних операција рачунара. На пример, неке од основних операција које се користе су: потребан број сабирања или множења; број поређења (компарација); изведени број замена меморијских локација; или број извршених машинских инструкција. Генерално, могли бисмо се реферисати само на извршење наведених основних операција.

Да ли је ово добар приступ за одређивање утрошка ресурс једног алгоритма? И да и не. Када су два алгоритма слична по утрошку времена, може да помогне прецизна функција која би одредила који је алгоритам бржи у датим условима. Али у многим случајевима је тешко или немогуће дати тачан аналитички опис потребног броја операција, нарочито када алгоритам извршава операције условно - у зависности од вредности улаза. Уместо тога, оно што је заиста важно није тачно време потребно да се изврши одређена функција, већ степен промене утрошка ресурса у зависности од улаза. Конкретно, размотрићемо две приказане функције које дају потребно време извршења у односу на величину улазног скупа података:

$f(n)=n^{3}-12n^{2}+20n+110$

$g(n)=n^{3}+n^{2}+5n+5$

Оне изгледају прилично различито, али како се понашају? Погледајмо неколико графика ових функција ($f(n)$ у црвеној, $g(n)$ у плавој боји):

Графикони f и g, за опсег 0 до 5	Графикони f и g, за опсег 0 до 15
Графикони f и g, за опсег 0 до 100	Графикони f и g, за опсег 0 до 1000

У првом, јако ограниченом графику криве изгледају различито. У другом криве крећу у сличном правцу, у трећем постоји само мала разлика и у последњем су скоро идентичне. У ствари оне се приближавају доминантном члану. Што је n веће, остали чланови постају мање значајни у односу на $n^{3}$. Као што се може видети, промена коефицијената чланова нижег реда алгоритма полиномијалног времена не помаже много. Оно што је стварно важно је коефицијент члана највишег реда. Зато смо усвојили посебну нотацију за ову врсту анализе. Тако је:

$f(n)=n^{3}-12n^{2}+20n+110=O(n^{3})$

Занемарујемо чланове нижег реда. Можемо да кажемо да је:

$O(\log {n})\leq O({\sqrt {n}})\leq O(n)\leq O(n\log {n})\leq O(n^{2})\leq O(n^{3})\leq O(2^{n})$

Ово нам пружа начин да лакше поредимо различите алгоритме. За сортирање $n$ елемената уметањем (insertion sort), потребно је реда величине $O(n^{2})$ корака. За сортирање спајањем (merge sort) потребно је $O(n\log {n})$ корака. Тако, ако је скуп улазних података довољно велик, сортирање спајањем је брже од сортирања уметањем.

Генерално пишемо да важи:

$f(n)=O(g(n))$

када је задовољено:

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n).$

Ово значи да $f(n)=O(g(n))$ важи ако и само ако постоје константе $c$ и $n_{0}$ веће од нуле, тако да за сваки $n>n_{0}$, $f(n)$ функција је позитивна и мања или једнака $cg(n)$. Приметимо да знак једнакости који се користи у горњем запису, описује релацију између $f(n)$ и $g(n)$ , а не истинску еквивалентност. У светлу тога, неки дефинишу велико О у терминима скупова, тако да је:

$f(n)\in O(g(n))$

када је:

$f(n)\in \{f(n):\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n)\}.$

Велико O нотација је само горња граница – супремум; оба следећа исказа су тачна:

$n^{3}=O(n^{4})$

$n^{4}=O(n^{4})$

Ако узмемо да знак једнакости означава еквиваленцију, добићемо јако чудан резултат, тј. да је:

$n^{3}=n^{4}$

што је очигледна бесмислица. Зато је дефиниција на бази теорије скупова згодна. Забуна може да се избегне тиме што ћете знак једнакости интерпретирати као једносмеран тј.:

$n^{3}=O(n^{4})$

не имплицира да важи и:

$O(n^{4})=n^{3}$

Увек држите О на десној страни знака једнакости.

Велико омега

Понекад нам није довољно да одредимо само горњу границу времена извршења неке функције. Велико омега нам даје доњу границу – инфинум. Генерално, кажемо да је:

$f(n)=\Omega (g(n))$

када важи:

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)\leq f(n).$

тј. $f(n)=\Omega (g(n))$ ако и само ако постоје константе c и n₀ такве да је за свако n>n₀, f(n) позитивна и већа или једнака cg(n). Тако, на пример, можемо да тврдимо да је:

$n^{2}-2n=\Omega (n^{2})$, (c=1/2, n₀=4) или

$n^{2}-2n=\Omega (n)$, (c=1, n₀=3),

али не можемо да је

$n^{2}-2n=\Omega (n^{3}).$

Велико тета

Када је дата функција истовремено и O(g(n)) и Ω(g(n)), кажемо да је Θ(g(n)), и тада имамо тесне границе функције. Функција f(n) је Θ(g(n)) када важи:

$\exists c_{1}>0,\exists c_{2}>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c_{1}\cdot g(n)\leq f(n)\leq c_{2}\cdot g(n),$

Али у већини случајева када покушавамо да утврдимо да је задата функција $f(n)=\Theta (g(n))$, уместо да користимо горњу дефиницију, показујемо да је она истовремено и O(g(n)) и Ω(g(n)).

Мало о и омега

Када асимптотске границе нису тесне, то можемо да изразимо тако што кажемо да је $f(n)=o(g(n))$ или $f(n)=\omega (g(n)).$. Дефинише се:

f(n) је o(g(n)) акко $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)<c\cdot g(n)$ и

f(n) је ω(g(n)) акко $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)<f(n).$

Приметимо да је функција f у o(g(n)) када за сваки коефицијент g, g на крају постаје већа од f, док је за O(g(n)) потребно да постоји један коефицијент за који g постаје најмање једнак f.

Анализа алгоритама: решавање диференцних једначина

За сортирање n елемената спајањем: $T(n)=2*T(n/2)+c(n)$. Ово описује једну итерацију сортирања: простор проблема $n$ се своди на две половине ($2*T(n/2)$), које се спајају по окончању свих рекурзивних позива ($c(n)$). Овај систем обележавања (нотација) је основа за анализу алгоритама, тако да треба што пре да се на њега навикнете. Постоје теореме које можете да користите да би проценили време великог О за функцију чија се диференцна (рекурентна) једначина уклапа и одређени шаблон.

Главна теорема

Razmotrimo diferencnu jednačinu koja se uklapa u formulu:

$T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$

зa a ≥ 1, b > 1 и k ≥ 0. Овде је a број рекурзивних позива за један позив функције, n је величина улаза, b је фактор за који се улаз смањује и k је полиномијални ред операције која се појављује сваки пут када се позове функција (осим за базне случајеве). На пример, код алгоритма сортирања спајањем, који ћемо покрити касније, имамо да је

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

зато што се два потпроблема позивају (решавају) за сваку итерацију случаја који није базни и величина вектора се сваки пут дели на пола. $O(n)$ је на крају „победнички“ део ове поделе и победнички алгоритам: он троши линеарно време за спајање резултата два рекурзивна позива у један коначни резултат.

Ако замислимо рекурзивне позиве T као формирање стабла, постоје три могућа случаја у којима може да се утврди где се већина времена извршења алгоритма троши („већина“ у смислу који се односи на његово асимптотско понашање):

1. стабло може да буде разгранато при врху и тада се већина времена се троши за време позива близу корена;
2. стабло може да буде уравнотежено, када је утрошак времена равномерно распоређен;
3. стабло може да буде разгранато при дну, када се већина времена троши на позиве близу листова.

У зависности од тога у ком се од три наведена статуса стабло налази, T ће имати другачију сложеност:

Главна теорема

Дато $T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$ for a ≥ 1, b > 1 and k ≥ 0:

• Ако је $a<b^{k}$, онда $T(n)=O(n^{k})\$ (разгранато при врху)
• Ако је $a=b^{k}$, онда $T(n)=O(n^{k}\cdot \log n)$ (уравнотежено)
• Ако је $a>b^{k}$, онда $T(n)=O(n^{\log _{b}a})$ (разгранато при дну)

За горњи случај сортирања спајањем

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

имамо да је

$a=2,b=2,k=1\implies b^{k}=2$

из чега следи да је $a=b^{k}$, што чини да је стабло уравнотежено. Према главној теореми сложеност сортирања спајањем је

$T(n)=O(n^{1}\log n)=O(n\log n)$.