Анализа алгоритама

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

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

У теоријској анализи алгоритама уобичајно је да се процењује њихова комплексност у асимпотском смислу, односно да процени функцију сложености за произвољно велики унос. Велико О нотација (Big O notation), Велико-омега нотација (Big-omega notation) и Велико-тета нотација (Big-theta notation) се користе у ову сврху. На пример, бинарна претрага подразумева неколико корака који су сразмерни логаритму дужине листе која се тражи, или у O(log(n)), једнако у логаритамском времену. Обично асимпотске процене се користе јер различите имплементације истог алгоритма могу да се разликују у ефикасности. Ефикасности било које две разумне имплементације датог алгоритма су повезане сталним мултипликативним фактором који се зове скривена константа.

Тачна, а не асимпотска мера ефикасности може понекад бити израчуната, али обично се захтевају израчунавања укључујући одређену имплементацију алгоритма, која се зове модел обрачуна. Овај модел израчунавања може бити дефинисан у смислу апстрактног рачунара, нпр. Тјурингова машина, и/или да се поједине операције извршавају у јединици времена.

На пример, ако се сортирана листа на коју се примењује бинарна претрага има n елемената, а ако гарантујемо да сваки проналазак елемената из листе може да се уради у јединици времена, онда најчешће log₂ n + 1 јединице времена су потребне да се врати одговор.

Модели трошкова

Ефикасност времена зависи од тога шта ћемо дефинисати да буде корак. За анализу корисно је да одговарају стварном времену извршавања, треба бити опрезан овде, на пример, неке анализе рачунају два корака као један. Ова претпоставка не може бити оправдана у одређеним ситуацијама. На пример, ако бројеви који су укључени у обрачун могу бити произвоњно велики, време које захтева један податак више не може да се претпоставља као константа.

Два модула обрачуна се обично користе:

Униформни модел трошкова, додељује стални трошак сваком машинском часу, без обзира на величину укључених бројева.
Логаритамски модел трошкова, додељује трошак машинском часу рада пропорционалном броју битова који су укључени.

Други модел је тежи за коришћење, и користи се само када је то потребно, на пример, у анализи произвољне прецизности аритметичких алгоритама, као и они који се користе у криптографији.

Кључна ствар која се често предвиђа је да објављене ниже границе за проблеме, често су модел обрачуна који је много рестриктивнији у односу на скуп операција које могу да се користе у пракси и због тога постоје алгоритми који су бржи од оног што се сматра могућим.

Извршна анализа

Извршна анализа је теоријска класификација која процењује и предвиђа повећање понестајућег алгоритма као повећање њговог улаза. Ова тема привлачи велику пажњу у рачунарском свету. Програм може одузети секунде, сати или чак године у циљу извршавања, у завсности од тога који алгоритам се примењује.

Недостаци емпиријских показатеља

С обзиром на то да су алгоритми независни од платформе (тј. дати алгоритам може бити реализован у произвољном прогамском језику на произвољном рачунару који користи произвољан оперативни систем) постоје значајни недостаци коришћења емпиријског приступа који мери компаративне перформансе датог скупа алгоритма.

Узимамо на пример програм који проналази одређену ставку сортирану у списку величине n, претпоставимо да овај програм реализован на рачунару А користећи алгоритам за линеарну претрагу, и рачунар Б који је спорији, и који користи алгоритам за бинарну претрагу. Мерење перфоманси на два рачунара која раде по свом програму може да изгледа отприлике овако.

n (величина)	Рачунар A време извршавања (у нано-секундама)	Рачунар Б време извршавања (у нано-секундама)
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000

На основу ових показатеља, лако би закључили да рачунар А далеко супериорнији у ефикасности од рачунара Б. Међутимм ако улазна величина расте у довољном броју, онда је овакав закључак погрешан.

n (величина)	Рачунар A време извршавања (у нано-секундама)	Рачунар Б време извршавања (у нано-секундама)
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10¹²	31,536 × 10¹² ns, или 1 година	1,375,000 ns, или 1.375 мили-секунда

Рачунар А, који користи линеарну претрагу програма, показује линеарну стопу раста. Време извршавања програма је директно пропорционално величини улаза. С друге стране, рачунар Б који користи бинарну претрагу програма, показује логаритамску стопу раста. Иако је рачунар А наводно бржи, рачунар Б ће неминовно премашити рачунар А који користи алгоритам са мањом стопом раста.

Правила раста

Неформално, за алгоритам се може рећи да показује стопу раста по налогу математичке функције, ако иза одређене улазне величине, функција f(n) пута позитивна контастанта предвиђа горњу границу или границе за извршење програма тог алгоритма. Другим речима, за улазну величину n од неког n₀ и константом C , време извршавања тог алгоритма никада неће бити већи од c × f(n). Овај концепт се често изражава у нотацији великог О. Велико О нотација је погодан начин да се изрази најгори сценарио за дати алгоритам, мада може да се користи и за просечне случајеве.

Емпиријски налози раста

Под претпоставком на време извршења, следи правило за напајање $\approx k n a$ , коефицијент a се може наћи узимањем емпиријских мера времена извршења $\{t1,t2\}$ за неки проблем величине $\{n1,n2\}$ , рачунајући $t_{2}/t_{1}=(n_{2}/n_{1})^{a}$ тако да $a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1})$ . Ако наредба раста заиста прати правило напајања, емпиријска вредност од а ће остати константна на различитим нивоима, ако не, то ће се променити, али и даље може да послужи за поређење било која два алгоритма. Примена је на табели

n (величина)	Рачунар A време извршавања (у нано-секундама)	редослед раста (n^_)	Рачунар Б време извршавања (у нано-секундама)	редослед раста (n^_)
15	7		100,000
65	32	1.04	150,000	0.28
250	125	1.01	200,000	0.21
1,000	500	1.00	250,000	0.16
...	...		...
1,000,000	500,000	1.00	500,000	0.10
4,000,000	2,000,000	1.00	550,000	0.07
16,000,000	8,000,000	1.00	600,000	0.06
...	...		...

Јасно се види да први алгоритам показује линеарно правило раста после правила за напајање. Емпиријске вредности за други алгоритам се брзо смањују, сугеришући да постоји још једно правило раста, и у сваком случају, емпријски посматрано, има мањи раст од оног првог.

Процена извршне комплексности

Извршна комплсност за најгори могући сценарио датог алгоритма може понекад бити оцењена испитивањем структуре алгоритма и доношењем неких поједностављених претпоставки. Размотримо следећи псеудокод:

1    get a positive integer from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

Рачунар ће дати дискретну количину времена за извршење сваког од упутства који су укључени у спровођење овог алгоритма. Одређени износ времена да спроведе дате инструкције разликоваће се у зависности од инструкција које се извршавају и који рачунар то врши, али је на класичном рачунару, овај износ ће бити детерминистички. Рецимо да радње које су спроведене у кораку 1 троше време Т1, корак 2 троши време Т2, и тако даље.

У алгоритму горе, кораци 1,2 и 7 само ће се једном извршити. За најгору могућу евалуацију, треба претпоставити да ће бити корак 3. Тако је укупан износ времена за покретање кораке 1-3 и 7 јесте:

T_{1}+T_{2}+T_{3}+T_{7}.\,

Петље у корацима од 4, 5 и 6 је теже проценити. Спољна петља у 4. кораку ће се извршити (n + 1) пута, који ће трошити Т4(n + 1) време. Унутрашња петља иде од 1 до n. На првом пролазу кроз спољашњу петљу, ј иде од 1 до 1. Унутрашња петља има један пролаз, па ради унутрашње тело петље (корак 6) троши време Т6, а унутрашња петља (корак 5) троши време 2Т5. Током наредног пролаза кроз спољашњу петљу, ј иде од 1 до 2, унутрашња петља има два места, тако да ради унутрашње тело петље (корак 6) троши време 2Т6, а унутрашња петља (корак 5) троши време 3Т5. Све у свему, укупно време потребно за покретање унутрашњег тела петље се може изразити као аритметичка прогресија:

T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}

које се може узети, као

T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]

Укупно време потребно за покретање унутрашње тела петље може бити слично:

2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}

=T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}

које се може узети, као

T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}=T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}=\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

Дакле укупно време извршавања овог алгоритма је:

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

које се своди на

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

Као правило палца, може се препоставити да највиши израз у свакој функцији истиче своју стопу раста и тиме дефинише своје бреме извршавања. У овом примеру n²је највиши реде, па се може закључити да је f(n) = O(n²). Формално се то може доказати на следећи начин

Prove that $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$

$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}$

$\leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}$ (for n ≥ 0)

Нека је к константа већа или једнака од[T₁..T₇]

$T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k$
$=2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}$ (for n ≥ 1) $=12kn^{2}$

стога $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}$ for $c=12k,n_{0}=1$ Елегантнији приступ анализи оваг алгоритам био би да се изјасне да [T₁..T₇] су сви једнаки јединици времена већа или једнака од[Т1 .. Т7]. Ово би значило да се време извршавања алгоритма разлаже на следећи начин:</ref>

$4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}$ (for n ≥ 1) $=O(n^{2}).$

Стопа раста анализе других ресурса

Методологије извршне анализе могу се користити за предвиђање и друге стопе раста, као што су конзумирање меморијског простора. Као пример, размотрите следећи псеудокод који управља и поново додељује заузеће меморије програмом на основу величине фајла којим овај програм управља:

while (file still open)

    let n = size of file
    for every 100,000 kilobytes of increase in file size
        double the amount of memory reserved

У овом случају, као што се величина датотеке n пута повећава, меморија се конзумира експоненцијалном стопом раста, што би O(2ⁿ). Ово је изузетно брза и вероватно неизводљива стопа раста за потрошњу меморијских ресурса.

Значај

Анализа алгориама је важна у пракси, јер случајно или ненамерно коришћење неефикасних алгоритама може значајно утицати на перформансе система. У временски осетљиве примене, алгоритму је потребно превише времена за покретање, што може да пружи застареле или бескорисне резултате. Неефикасан алгоритам може захтевати нерационалну велику количину рачунарске моћи или складиштења како би се управљало, чинећи га практично неупотребљивим.

Види још

Референце

Литература

Hromkovi, Juraj (2004). Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer. стр. 177—. ISBN 978-3-540-14015-3.
Tarjan, Robert Endre (1983). Data Structures and Network Algorithms. SIAM. стр. 3—. ISBN 978-0-89871-187-5.
Ausiello, Giorgio (1999). Complexity and Approximability Properties: Combinatorial Optimization Problems and Their Approximability Properties. Springer. стр. 3—. ISBN 978-3-540-65431-5.