Алгоритамска сложеност

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

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

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

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

Почнимо са мало мотивисања теме.

Мотивација[уреди | уреди извор]

Већ знамо да постоје програми за мерење брзине извршавања програма. Ти програми се називају профајлери и мере потребно време извршавања у милисекундама, те нам помажу при оптимизацији кода. Иако је ово средство корисно, није баш важно за алгоритамску сложеност. Сложеност алгоритма је нешто креирано за поређење два алгоритма на нивоу идеје - игнорисањем детаља ниског нивоа, као што је имплементација програмског језика, хардвера на коме се алгоритам покреће или скупа инструкција датог процесора. Циљ је да се упореди алгоритам у његовом смислу: Идеје како се израчунава тако нешто. Бројање милисекунди неће нам помоћи у томе. Сасвим је могуће да лош алгоритам написан у програмском језику ниског нивоа као што је асемблер ради много брже него добар алгоритам написан у језику високог нивоа као што су Пајтон или Руби. Тако да је време да се дефинише шта "бољи алгоритам" заиста јесте.

Алгоритми су програми који обављају само рачунање, а не друге ствари које рачунари често раде, као што су умрежавање задатака или кориснички унос и приказ. Анализа сложености омогућава да се измери колико је брз програм када се обавља израчунавање. Примери операција које су чисто рачунске и укључују нумеричке операције са децималним бројевима, као што сабирање и множење; претраживање базе података која се уклапа у РАМ за дате вредности; одређивање путање лика са вештачком интелигенцијом којом ће ходати у видео игрици, тако да пређе кратко растојање у свом виртуелном свету (види слику 1); или претрага регуларног израза у низу. Јасно, рачунање је свеприсутно у рачунарским програмима.

Анализа сложености је такође алат који објашњава како се алгоритам понаша када унос расте. Ако убацујемо различите уносе, како ће се понашати алгоритам? Ако нашем алгоритму треба 1 секунда да заврши за унос величине 1000, како ће се понашату ако се удвостручи величина уноса? Да ли ће се покренути истом брзином, пола од те брзине, или четири пута спорије? У практичном програмирању, ово је важно јер нам омогућава да предвидимо како ће се понашати наш алгоритам када унос података постаје све већи. На пример, ако смо направили алгоритам за веб апликацију која ради добро са 1000 корисника и мери своје време рада, користећи анализу сложености алгоритма имаћемо прилично добру представу о томе шта ће се десити када се број будео попео на 2000 корисника. За алгоритамска такмичења, анализа сложености нам даје увид о томе колико дуго ће се наш код извршавати за највеће тестиране вредности које служе за тестирање исправност нашег програма. Дакле, ако меримо понашање нашег програма за мали унос, можемо добити добру идеју како ће се понашати за веће уносе. Почнимо од једноставног примера: Проналажење максималног елемента у низу.

Бројање инструкција[уреди | уреди извор]

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

Максимални елемент у низу може се потражити помоћу једноставног кода као што је овај јаваскрипт код. Дат је улаз низа А величине n:

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {
   if ( A[ i ] >= M ) {
       M = A[ i ];
   }
}

Сада, прва ствар коју ћемо урадити је да избројимо

колико основних инструкција тај део кода извршава. Ми ћемо то учинити само једном и то неће бити потребно како будемо развијали теорију. За анализирање овог кода, поделићемо га на мање делове; ствари које може процесор директно да извршава - или барем близу томе. Претпоставићемо да наш процесор може извршити следеће операције као једна инструкција за сваку:

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

Претпоставимо да се гранање (избор између „иф" и „елсе" делова кода после

израчунавања „иф") јавља одмах и нећемо рачунати ову инструкцију. У горњем коду, прва линија кода је:

var M = A[ 0 ];

Ово захтева 2 инструкције: једна за претрагу A[ 0 ] и друга за додељивање вредности М ( под претпоставком да је n увек барем 1). Ове две инструкције су увек захтеване од алгоритма, без обзира на вредност n. Почетни код „фор" петље такође мора да увек ради. То нам даје још две инструкције: доделу и поређење:

i = 0;
i < n;

Ово ће се покренути пре првог проласка кроз „фор" петљу. Након сваке итерације петље, имамо још две инструкције за покретање: повећање i и провера да ли ћемо остати у петљи:

++i;
i < n;

Дакле, ако занемаримо тело петље, број инструкција овог алгоритма је 4 + 2n.

То је, 4 инструкције на почетку петље и 2 инструкције на крају сваке итерације којих имамо n. Сада можемо дефинисати математичку функцију f( n ) тако да за дато n враћа број инструкција потребних алгоритму.

За празно тело петље, имамо f( n ) = 2n + 4.

Анализа најгорег случаја[уреди | уреди извор]

Сада, гледајући тело петље, имамо операцију претраге низа и поређење које се увек извршава:

if ( A[ i ] >= M ) { ...

То су две инструкције. Али, „иф" тело се може покренути, али и не мора, зависно од тога које су вредности низа. Ако се деси да је A[ i ] >= M, онда ћемо покренути ове две додатне инструкције - претрагу низа и доделу:

M = A[ i ];

Али сада не можемо дефинисати f( n ) тако лако, јер наш број инструкција не зависи само од n, већ и од нашег улаза. На пример, за A = [ 1, 2, 3, 4 ] алгоритму је потребно више инструкција него за A = [ 4, 3, 2, 1 ]. Приликом анализе алгоритма, често у разматрање узимамо најгори случај. Шта је најгоре што се може десити за алгоритам? Када нашем алгоритам треба највише инструкција да се заврши? У овом случају, то је када имамо низ у растућем редоследу, као што је A = [ 1, 2, 3, 4 ]. У том случају, M треба да се замени сваки пут и то даје највише инструкција. Рачунарски научници имају фенси име за то и они га називају анализа најгорег случаја; то је ништа више него да узимамо у обзир случај када имамо најмање среће. Дакле, у најгорем случају, имамо 4 инструкције унутар тела петље, тако да имамо f( n ) = 4 + 2n + 4n = 6n + 4. Ова функција f, у зависности од величине проблема n, даје нам број инструкција које ће бити потребне у најгорем случају.

Асимптотско понашање[уреди | уреди извор]

С обзиром на такву функцију, имамо прилично добру идеју о томе колико је брз алгоритам. Међутим, неће бити потребе да прођемо кроз тежак задатак бројања инструкција у нашем програму. Осим тога, број стварно потребних процесорских инструкција за сваку изјаву програмског језика зависи од преводиоца нашег програмског језика и од доступних перформанси процесора (односно да ли је АМД или Интел Пентиум на рачунару, или МИПС процесор на Плејстејшну 2), а то ћемо да игноришемо. Сада ћемо покренути нашу "f" функцију кроз "филтер" који ће помоћи да се отарасимо оних мањих детаља које рачунарски научници воле да игноришу.

У нашој функцији, 6n + 4, имамо два услова: 6n и 4. У анализи сложености занима нас само шта се дешава са функцијом бројања инструкција за повећане улаза програма ( n ). Ово стварно иде заједно са претходним идејама понашања "најгорег случаја": занима нас како се наш алгоритам понаша у тежим случајевима; када је изазван да уради нешто теже. Обратите пажњу да је ово заиста корисно да се упореде алгоритами. Ако алгоритам победи други алгоритам за велики улаз, вероватно је да бржи алгоритам остаје бржи за мање уносе. Из услова које посматрамо, одбацићемо све услове који спорије расту и задржатаћемо се само на оне који расту брзо како n постаје све већи. Јасно је да 4 остаје 4 како n расте, али 6n се повећава све више и више, тако да тежи да вреди више и више за веће проблеме. Дакле, прва ствар коју ћемо урадити је да одбацимо 4 и узмемо функцију f( n ) = 6n.

То има смисла, ако размислите о томе, јер је 4 "константа за иницијализацију". Различитим програмским језицима треба различито време да се покрену. На пример, Јави треба неко време да покрене своју виртуелну машину. Пошто игноришемо разлике у програмским језицима, можемо игнорисати и ову вредност.

Друга ствар коју ћемо игнорисати је константа множења испред n, па ће наша функција сада бити f( n ) = n. Као што можете видети ово поједностављује

ствари доста. Опет, има смисла да константу множења одбацимо ако размишљамо о томе како различити програмски језици преводе. "Претраживање низа" инструкција на једном језику може се превести на различите инструкције у другом програмском језику. На пример, у C, A[ i ] не обухвата проверу да је i у декларисаној величини низа, док у Паскалу то ради. Дакле, следећи код у паскалу:

M := A[ i ]

и њему еквивалентан код у C-у:

if ( i >= 0 && i < n ) {
   M = A[ i ];
}

Разумно је очекивати да ће различити програмски језици имати различите факторе када рачунамо њихове инструкције. У нашем примеру у којем смо користили лош компајлер за Паскал, јасно је да је могућа оптимизација, Паскал захтева 3 инструкције за сваки приступ низу уместо 1 инструкције коју C захтева. Изостављање овог фактора иде са игнорисањем разлике између појединих програмских језика и компајлера и остаје само анализа идеје самог алгоритма.

Овај филтер "игнорисања свих фактора" и "задржавања највећег растућег услова" како је горе описано је оно што зовемо асимптотско понашање. Дакле, асимптотско понашање f( n ) = 2n + 8 је функција f( n ) = n. Математички гледано, кажемо да нас занима лимит функције f како n тежи бесконачности. (Узгред, у строгом математичком окружењу, ми не би могли да одбацимо константу у лимиту, али за рачунарске потребе науке, радимо то из разлога који је горе наведен.)

Пронађимо асимптотско понашање на примерима функција одбацивањем константи и задржавањем услова најбржег раста.

**Слика 2:** n³ функција, нацртана плавом, постаје већа него 1999n функција, нацртана црвеном, после n = 45. После те тачке остаје већа заувек.

f( n ) = 5n + 12 даје f( n ) = n. Разлог је наведен горе.
f( n ) = 109 даје f( n ) = 1. Одбацујемо множење 109 * 1, али остављамо 1 овде да укажемо на то да ова функција има не-нултну вредност
f( n ) = n² + 3n + 112 даје f( n ) = n²Овде, n² расте брже од n за довољно велико n, па узимамо то.
f( n ) = n³ + 1999n + 1337 даје f( n ) = n³Иако је фактор испред n прилично велики, још увек можемо наћи довољно велико n, тако да је n³веће од 1999n. Како смо заинтересовани за понашање за веома велике вредности n, узимамо само n³ (види слику 2).
f( n ) = n + ${\textstyle {\sqrt {n}}}$ даје f( n ) = n То је зато што n расте брже од ${\textstyle {\sqrt {n}}}$ како повећавамо n.

Можете испробати следеће примере:

Вежба 1

f( n ) = n⁶ + 3n
f( n ) = 2ⁿ + 12
f( n ) = 3ⁿ + 2ⁿ
f( n ) = nⁿ + n

Ако имате проблема са неким задатком горе, користите неко велико n и упоредите резултате.

Сложеност[уреди | уреди извор]

Пошто игноришемо све ове декоративне константе, постаје прилично лако предвидети асимптотско понашање функције бројања инструкција програма. У ствари, сваки програм који нема петљу ће имати f( n ) = 1, јер је број потребних инструкција само константа (осим ако се користи рекурзију; види доле). Било који програм са једном петљом која иде од 1 до n имаће f( n ) = n, јер ће бити константан број инструкција пре петље, константан број инструкција после петље, и константан број инструкција унутар петље која се покреће n пута.

Ово би сада могло бити много лакше и мање напорно од бројања појединачних инструкција, па хајде да

погледамо неколико примера да се упознамо са овим. Следећи PHP програм проверава да ли одређена вредност постоји у оквиру низа А величине n:

<?php
$exists = false;
for ( $i = 0; $i < n; ++$i ) {
   if ( $A[ $i ] == $value ) {
       $exists = true;
       break;
   }
}
?>

Овај метод претраживања вредности у низу зове се линеарна претрага.

Ово је разумно име, јер овај програм има f( n ) = n ( дефиниција шта "линеарно" значи је у следећем одељку). Можете приметити да постоји "break" изјава овде која може да раније прекине програм, чак и после једног понављања. Али како нас занима најгори случај, односно у овом случају је то да се у низу А не налази вредност. Дакле, још увек имамо f( n ) = n.

Вежба 2

Систематски анализирајте броја инструкција горњег PHP програма, треба у односу на n у најгорем случају да буде f( n ), слично како смо анализирали наш први јаваскрипт програм. Затим проверите то, да, асимптотски имамо f( n ) = n.

Погледајмо Пајтон програм који сабира два елемената низа и даје збир те две променљиве у нову променљиву:

v = a[ 0 ] + a[ 1 ]

Овде имамо константан број инструкција, тако да имамо f( n ) = 1. Следећи програм у C++ проверава да ли вектор (фенси низ) под називом А величине n садржи исте две вредности било где у њему (дупликате):

bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
   for ( int j = 0; j < n; ++j ) {
       if ( i != j && A[ i ] == A[ j ] ) {
           duplicate = true;
           break;
       }
   }
   if ( duplicate ) {
       break;
   }
}

Како овде имамо две угњеждене петље, једна унутар друге, имаћемо асимптотско понашање описано са f( n ) = n²

Правило:
Једноставни програми могу се анализирати бројањем угњеждених петљи у
програму. Једна петља од n елемената даје f( n ) = n. Петља у оквиру
петље приноси f( n ) = n². Петља у петљи у оквиру петље приноси f( n ) = n³.

Ако имамо програм који позива функцију у оквиру петље и знамо број инструкција које позвана функција обавља, лако је утврдити број инструкција целог програма. Заиста, хајде да погледамо овај C пример:

int i;
for ( i = 0; i < n; ++i ) {
   f( n );
}

Ако знамо да је f( n ) функција која обавља тачно n инструкција, онда можемо знати да је број инструкција читавог програма асимптотски n², како је функција тачно n пута звана.

Правило:
За дату серију петљи које су у низу, најспорија од њих одређује асимптотско понашање програма. Две угнежђене петље праћене једном петљом су асимптотски исте као угњеждене петље саме, јер угњеждене петље
доминирају у односу на једноставну петљу.

Када смо схватили шта је f асимптотски, рећи ћемо да је наш програм Θ( f( n ) ).

На пример, наведени програми су Θ( 1 ), Θ( n2 ) и Θ( n² ) респективно. Θ( n ) се изговара "тета од n". Понекад можемо рећи да је f( n ), оригинална функција бројења инструкција, укључујући константе, је Θ (нешто). На пример, можемо рећи да је f( n ) = 2n функција која је Θ( n ) - ништа ново овде. Такође можемо записати 2n ∈ Θ( n ), који се изговара као "два n припада тета од n". Све што нотација говори је да ако смо рачунали број потребних инструкција програма и он је 2n, онда асимптотско понашање нашег алгоритма је описано са n, које смо нашли изостављањем константе . Са овом нотацијом дате су неке праве математичке изјаве:

n⁶ + 3n ∈ Θ( n⁶ )
2ⁿ + 12 ∈ Θ( 2ⁿ )
3ⁿ + 2ⁿ ∈ Θ( 3ⁿ )
nⁿ + n ∈ Θ( nⁿ )

Узгред, ако сте решили вежбу 1 горе, ово су управо одговори које је требало да добијете.

Ову функцију називамо, односно оно што смо ставили Θ(овде), временска сложеност или само сложеност нашег алгоритма. Дакле алгоритам са Θ (n) је сложености n. Такође имамо посебне називе за Θ (1), Θ (n), Θ ( n² ) и Θ( log( n ) ), јер се појављују врло често. Кажемо да је Θ (1)

алгоритам константно-временски алгоритам, Θ ( n ) је линеарни, Θ ( n² ) је квадратни и Θ( log( n ) ) је логаритамски.

Правило: Програм са већим Θ ради спорије него програм са мањим Θ.

Велико О нотација[уреди | уреди извор]

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

Познати проблем који рачунарски научници користе за учење алгоритама је проблем сортирања. У проблему сортирања, низ А величине n је дат (звучи познато?) и тражи се да напишемо програм који сортира овај низ. Овај проблем је интересантан јер је прагматичан проблем у реалним системима. На пример, читач докумената треба да сортира фајлове по имену, тако да корисник може лако да се сналази међу њима. Или, као други пример, у видео игри може бити потребно сортирање 3Д објеката приказаних у свету на основу њихове удаљености од ока играча унутар виртуелног света како би се утврдило шта је видљиво, а шта није, нешто што се зове проблем видљивости (види слику 3). Предмети који се испоставе да су најближи играчу су они видљиви, док они даљи могу добити скривени предмети. Сортирање је такође интересантно јер постоје многи алгоритми који га решавају, од којих су неки гори од других. Такође је једноставан проблем дефинисати и

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

b = []
n.times do
    m = a[ 0 ]
    mi = 0
    a.each_with_index do |element, i|
        if element < m
            m = element
            mi = i
        end
    end
    a.delete_at( mi )
    b << m
end

Овај метод се назива сортирање избором. Он налази минимум нашег низа (низ је означаен горе, док је минимална вредност означена са m, а mi је њен индекс), ставља га на крај новог низа (у нашем случају b),

и уклања га из оригиналног низа. Онда проналази минимум између осталих вредности нашег оригиналног низа, додаје ја у наш нов низ тако да он сада садржи два елемента, и уклања га из нашег оригиналног низа. Наставља овај процес док сви предмети не буду уклоњени из оригиналног низа и убачени у нови низу што значи да је низ је сортиран. У овом примеру, видимо да имамо две угњеждене петље. Спољна петља ради n пута, а унутрашња петља ради једном за сваки елемент низа а. Док низ а првобитно има n елемената, уклањамо по један елемент у свакој итерацији. Тако да се унутрашња петља понавља n пута током прве итерације спољашње петље, а затим n - 1 пута, онда n - 2 пута и тако даље, до последњег понављања спољашње петље током које ради само једном.

Мало је теже проценити сложеност овог програма, као што смо морали да пронађемо збир 1 + 2 + ... + (n - 1) + n. Али можемо са сигурношћу знати "горњу границу" за њега. То јест, можемо мењати наш програм да буде гори него што јесте, а онда наћи сложеност тог новог програма који смо извели. Ако можемо наћи сложеност горег програма који смо изградили, онда знамо да је наш оригинални програм највише толико лош, или можда бољи. На тај начин, ако нађемо прилично добру сложеност за наш измењен програм, који је гори него оригинални, можемо знамо да ће наш оригиналан програм имати прилично добру сложеност- било добар као наш измењени програм или још бољи.

Нађимо начин да изменимо пример програма да би лакше дошли до његове сложености. Али имајмо на уму да можемо само погоршати, односно учинити га са више инструкција, тако да је наша процена значајна за наш оригиналан програм.Јасно је да можемо мењати унутрашњу петљу програма да се увек понавља тачно n пута уместо различитог број пута. Нека од ових понављања ће бити бескорисна, али то ће нам помоћи при анализи сложености резултујућег алгоритма. Ако направимо ову једноставну промену, онда је нови алгоритам који смо изградили Θ( n² ), јер имамо две угњеждене петље где се свака понавља тачно n пута. Ако је тако, кажемо да је оригинални алгоритам O( n² ). O( n² ) се изговара "велико О од n на квадрат". Ово говори да наш програм асимптотски није гори него n². Може бити бољи од тога, или може бити исти као то. Узгред, ако је наш програм заиста Θ( n² ), можемо даље тврдити да је О( n² ). Да схватите то да, замислите мењање оригиналног програма на начин на који то не мења много, али ипак чини мало горе, као што је додавање бесмислене инструкције на почетку програма. Овако ће се променити функција бројања инструкција простом константом, која се игнорише када је у питању асимптотско понашање. Дакле, програм који је Θ( n² ) је такође O( n² ). Али програм који је O( n² ) не мора бити и Θ ( n² ). На пример, било програм који је Θ ( n ) је такође О ( n² ) поред тога што О ( n ). Ако замислимо да Θ( n ) програм је једноставна петља која се понавља n пута, а можемо направити горе тако што ћемо је угнездити у другу петљу која се понавља n пута, и на тај начин производећи програм са f( n ) = n². Да би то генерализовали, сваки програм који је Θ( a ) је О( b ) када је b горе него a. Обратите пажњу да наша промена у програму не мора да нам врати програм који је заправо смислен или еквивалентан нашем оригиналном програму. Већ само треба да обави више инструкција него оригинални за дато n. Све што користимо за бројање инструкција, заправо није решење нашег проблема.

Дакле, рекавши да је наш програм O( n² ) био на сигурној страни: Анализирали смо наш алгоритам, и открили да никада неће бити гори од n². Али, могуће је да је то, у ствари, n². То нам даје добру процену колико брзо наш програм ради. Следи неколико примера да вам помогне да се упознате са овим новим ознакама.

Вежба 3

Наћи која је од следећих изјава тачна:

A Θ( n ) алгоритам је O( n )
A Θ( n ) алгоритам је O( n² )
A Θ( n² ) алгоритам је O( n³ )
A Θ( n ) алгоритам је O( 1 )
A O( 1 ) алгоритам је Θ( 1 )
A O( n ) алгоритам је Θ( 1 )

Решење

Знамо да је тачно као што је наш оригиналан програм био Θ( n ). Можемо постићи O( n ) без икакве измене нашег програма.
Како је n² горе него n, ово је тачно.
Како n³ горе него n², ово је тачно.
Како1 није горе од n, ово је нетачно. Ако програму треба n инструкцијаасимптотски (линеаран број инструкција), не можемо учинити горе и иматисамо 1 инструкцију асимптотски (константан број инструкција).
Ово је тачно како су две сложености једнаке.
Овоможе, а и не мора бити тачно у зависности од алгоритма. У општемслучају је нетачно. Ако је алгоритам Θ( 1 ), онда је јасно O( n ). Алиако је O( n ) онда не мора бити Θ( 1 ). На пример, Θ( n ) алгоритам јеО( n ) али није Θ( 1 ).

Вежба 4

Користитећи суму аритметичке прогресије доказати да програм изнад није само O( n² ), него и Θ ( n² ). Пошто О-сложеност алгоритма даје горњу границу за стварне сложености алгоритма, док Θ даје стварну сложеност алгоритма, понекад кажемо да нам Θ даје чврсту границу. Ако знамо да сложеност границе која није чврста, такође можемо користити мало о да означимо то. На пример, ако је алгоритам Θ( n ), онда је чврста сложеност n. Онда је овај алгоритам и O( n ) и O( n² ). Пошто је алгоритам Θ( n ), O( n ) је чврста граница. Али O( n² ) ако није везано чврсто, онда можемо написати да је алгоритам o( n2 ), што се изговара "мало о од н на квадрат" да илуструје да наша веза није чврста. То је боље ако можемо да пронађемо чврсте границе за наш алгоритам, како нам даје више информација о томе како се наш алгоритам понаша, али то није увек лако урадити.

Вежба 5

Одредите које од следећих граница су чврсте границе и који нису чврсте границе. Проверите да ли границе могу да буду погрешне. Користите о (нотацију) да илуструјете границе које нису чврсте.

A Θ( n ) је алгоритам за који смо нашли да је O( n ) горња граница.
A Θ( n² ) је алгоритам за који смо нашли да је O( n³ ) горња граница.
A Θ( 1 ) је алгоритам за који смо нашли да је O( n ) горња граница.
A Θ( n ) је алгоритам за који смо нашли да је O( 1 ) горња граница.
A Θ( n ) је алгоритам за који смо нашли да је O( 2n ) горња граница.

Решење

У том случају, сложеност Θ и сложеност О су исти, тако да граница чврста.
Овде видимо да је сложеност О већих размера него сложеност Θ тако да граница није чврста. Заиста, граница за O( n² ) ће бити чврста. Тако можемо написати да је алгоритам o( n³ ).
Опетвидимо да сложеност О већих размера него сложеност Θ тако да имамограницу која није чврста. Граница за О (1) ће бити чврсто један. Дакле, можемо истаћи да граница O( n ) није чврста записивањм o( n ) .
Морада смо направили грешку у обрачуну ове границе, јер је погрешно. Немогуће је за Θ( n ) алгоритам да има горњу границу О (1), како је n већа сложеност од 1. Запамтите да О даје горњу границу.
Томоже изгледати као граница која није чврста, али то није истина. Овагранице је у ствари чврста. Подсетимо да је асимптотско понашање 2n и nисто, а то О и Θ су само забринути са асимптотским понашањем. Тако имамода је O( 2n ) = O( n ) и стога је ово граница је чврста како јекомплексност иста као и Θ.

Правило: Лакше је разумети О сложенот алгоритма него Θ сложеност

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

лош. Ово може бити такође корисно да се утврди да је алгоритам преспор за употребу у конкретном случају. На пример, ако се каже да је алгоритам је Ω( n³ ) то значи да алгоритам није бољи од n³. Може бити Θ( n³ ), лош као Θ( n⁴ ) или још гори, али знамо да је бар донекле нешто лоше. Тако нам Ω даје доњу границу за сложеност нашег алгоритма. Слично као ο, можемо записати ω ако знамо да наша граница није чврста. На пример, Θ( n³ ) алгоритам је ο( n⁴ ) и ω( n² ). Ω( n ) се чита "велико омега од n", док се ω (n) изговара "мало омега од n"

Вежба 6

За Θ сложеност напишите чврсту и не-чврсту O границу, и чврсту и не-чврсту Ω границу по вашем избору, под условом да постоје.

Θ( 1 )
Θ( ${\textstyle {\sqrt {n}}}$ )
Θ( n )
Θ( n² )
Θ( n³ )

Решење

Ово је праволинијска примена горе наведених дефиниција.

Чврста граница ће бити О (1) и Ω (1). Не-чврста О-граница биће О (n ). Подсетимо се да нам О даје горњу границу. Како је nвећег обима од 1 ово је не-чврста граница и можемо је записати као о( n). Али не можемо да нађемо не-чврсту границу за Ω, јер не можемо добитимање од 1 за ове функције. Дакле, мораћемо да радимо са чврстомграницом.
Чврста граница ће морати да буде иста као сложеност Θ, тако да је O( ${\textstyle {\sqrt {n}}}$ ) и Ω( ${\textstyle {\sqrt {n}}}$ ), респективно. За не-чврсту границу можемо имати O( n ), како је n веће од ${\textstyle {\sqrt {n}}}$ тако да је горња граница за ${\textstyle {\sqrt {n}}}$ . Као што знамо ова не-чврста горња граница се може записати и као о( n). За доњу границу која није чврста, можемо једноставно користити Ω( 1). Као што знамо да та граница није чврста, можемо записати као ω( 1 ).
Чврстегранице су O( n ) и Ω( n ). Две не-чврсте границе могу бити ω( 1 ) ио( n3 ). То су у ствари прилично лоше границе, јер су далеко одоригиналних сложености, али и даље важе по нашим дефиницијама.
Чврсте границе су O( n2 ) и Ω( n2 ). За не-чврсте границе смо опет могли користити ω( 1 ) и o( n³ ) као у нашем претходном примеру.
Чврсте границе су O( n³ ) и Ω( n³ ) респективно. Две не-чврсте границе могу бити ω( ${\textstyle {\sqrt {n}}}$ n² ) и o( ${\textstyle {\sqrt {n}}}$ n³ ). Иако ове границе нису блиске, боље су од оних које смо горе навели.

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

Такође имајте на уму да, иако Ω нам даје доњу границу за понашање наше функције (тј. побољшали смо наш програм тако да обавља мање инструкција) и даље гледамо на анализу "најгорег случаја". Из разлога што у наш програм убацујемо најгори могући унос за дато n и анализирамо његово понашање под претпоставком. Следећа табела приказује симболе које смо увели и њихову преписку са математичким симболима поређења које користимо за бројеве. Разлог зашто не користимо уобичајене симболе овде, већ користимо грчка слова, јесте да истакнемо да поредимо асимптотско понашање, а не само просто поређење.

Оператор асимптотског поређења	Оператор бројевног поређења
Алгоритам је o( нечег )	Број је < од нешто
Алгоритам је O( нечег )	Број је ≤ нешто
Алгоритам је Θ( нечег )	Број је = нешто
Алгоритам је Ω( нечег )	Број је ≥ нешто
Алгоритам је ω( нечег )	Број је > од нешто

Правило: Док су сви симболи O, o, Ω, ω и Θ корисни, O се највише користи, јер је лакши за одлучивање од Θ и више практичнији него Ω.

Логаритми
[уреди | уреди извор]

**Слика^{[мртва веза]} 4:** Поређење функција n, ${\textstyle {\sqrt {n}}}$ , и log( n ). Функција n је линеарна функција, нацртана зеленом на врху, расте много брже него функција квадратног корена, нацртана црвеном у средини, за коју се испоставља да расте много брже него log( n ) функција нацртана плавом на дну слике. чак и за мало n као што је n = 100, разлике су прилично приметне.

Ако знате шта логаритми су, слободно прескочите овај део. Како много људи није упознато са логаритмима, или их нису само користили много недавно и заборавили их, овај део овде је увод за њих.

Логаритми су важнијер се јављају често приликом анализирања сложености. Логаритам је операција примењена на број и чини га доста малим - слично као квадратни корена неког броја. Дакле, ако постоји једна ствар коју желите да запамтите о логаритама је да они узимају број и чине га много мањим од оригиналног (види слику 4). Сада, на исти начин на који је квадратни корен супротна операција од квадрирања нечег, логаритми су супротна операција од експонента. Пример: погледајте једначину:

2^x = 1024

Сада желимо да решимо једначину за x. Питамо се: На који број треба да погиднемо 2 да би добили 1024? Тај број је 10. Стварно, имамо 2¹⁰ = 1024, што је лако потврдити. Логаритми нам помажу да забележимо овај проблем употребом нове нотације. У овом случају, 10 је логаритам од 1024 то пишемо као log( 1024 ), а то читамо "логаритам 1024". Због употребе 2 као базе, овај логаритам се зове логаритам са основом 2. Постоје логаритми са другим базама, али у овом чланку ћемо користити само базу 2. У рачунарству, база 2 логаритма је чешћа него остале основе алгоритма. Разлог је зато што често имамо само два основна ентитета: 0 и 1. Такође желимо да велики проблем поделимо на пола. Тако да за овај чланак све што је потребно да знате јесте само логаритам са основом (базом) 2.
Вежба 7

Реши једначине испод. Означите логаритам који тражите у сваком наведеном случају. Користите основу 2.

2^x = 64
(2²)^x = 64
4^x = 4
2^x = 1
2^x + 2^x = 32
(2^x) * (2^x) = 64

Решење

Не постоји ништа више од примене идеае дефинисаних горе.

Методом покушаја и грешака можемо наћи да је x = 6 и log( 64 ) = 6.
Овде смо приметили да (2²)^x по особинама експонената, може бити записано као 2^2x. Тако имамо да је 2x = 6 јер је log(64) = 6 из претходног резултат и зато је х = 3.
Користећи своје знање из претходне једначине, можемо да напишемо 4 као 2² и тако наш једначина постаје (2²)^x = 4 која је иста као и 2^2x = 4. Онда приметимо да је log( 4 ) = 2 јер је 2² = 4 и стога имамо да је 2^x = 2. Дакле, x = 1. Ово је лако приметити из оригиналне једначине, користећи експонент 1 даје основу као резултат.
Подсетимо се да експонент 0 даје резултат 1. Дакле, имамо log( 1 ) = 0 kao 2⁰ = 1, па је x = 0.
Овде имамо збир па не можемо узети директно логаритам. Међутим, приметимо да је 2^x + 2^x је исто као 2 * (2^x). Тако смо помножили за два, што је исто као 2^x ^{+ 1} и сада све што морамо да урадимо је да решимо једначину 2^{x + 1} = 32. Налазимо да је log(32) = 5, односно x + 1 = 5, а самим тим да је x = 4.
Како множимо заједно два пута 2 на неки степен, можемо да их придружимо, тј. (2^x) * (2^x) је исти што и 2^2x. И онда све што треба је да решимо једначину 2^2x = 64 која је већ решена горе за x = 3.

Правило: За поређење алгоритма реализованих у C++, једном када анализирате сложеност, можете добити грубу процену колико брзо ће ваш програм радити очекујући да обавља око 1.000.000 операција у секунди, где су операције које бројите дате понашањем асимптотске функције описујући ваш алгоритам. На пример, Θ ( n ) алгоритам траје око једне секунде да обради улаз за n = 1.000.000.

Рекурзивна сложеност[уреди | уреди извор]

**Слика 5:** Рекурзија са функцијом факторијела.

Погледајмо сада рекурзивну функцију. Рекурзивна функција је функција која позива саму себе. Можемо ли анализирати сложеност? Наредна функција, написана у Пајтону, рачуна факторијел броја. Факторијел позитивног целог броје се налази тако што се тај број множи са бројем за 1 мањим од њега, и то се понавља све док не дође до 1. На пример, факторијел од 5 је 5 * 4 * 3 * 2 * 1. То записујемо "5!", а читамо као"5 факторијел".

def factorial( n ):
    if n == 1:
        return 1
    return n * factorial( n - 1 )

Анализирајмо сложеност ове функције. Ова функција нема петље, али њена комплексност није ни константна. Оно што треба да урадимо да бисмо сазнали њену сложеност је да се вратимо на бројање инструкција. Јасно, ако убацимо неко n у ову функцију, она ће се извршити n пута. Ако нисте сигурни за то, прођите "ручно" са n = 5 да потврдите да заправо ради. На пример, за n = 5, она ће извршити 5 пута, јер ће задржати смањење n за 1 у сваком позиву. Можемо дакле да видимо да је ова функција онда Θ ( n ).

Ако нисте сигурни о то, запамтите да увек можете да пронађете тачну сложеност бројањем инструкција. Ако желите, покушајте да избројите стварне инструкција које обавља ова функција да добијете функцију f( n ) и видите да је то заиста линеарна ( присетимо се да линеарно значи Θ ( n )).

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

Анализирајмо сложеност ове функције. Ова функција нема петље, али њена комплексност није ни константна. Оно што треба да урадимо да бисмо сазнали њену сложеност је да се вратимо на бројање инструкција. Јасно, ако убацимо неко n у ову функцију, она ће се извршити n пута. Ако нисте сигурни за то, прођите "ручно" са n = 5 да потврдите да заправо ради. На пример, за n = 5, она ће извршити 5 пута, јер ће задржати смањење n за 1 у сваком позиву. Можемо дакле да видимо да је ова функција онда Θ ( n ). Ако нисте сигурни о то, запамтите да увек можете да пронађете тачну сложеност бројањем инструкција. Ако желите, покушајте да избројите стварне инструкција које обавља ова функција да добијете функцију f( n ) и видите да је то заиста линеарна ( присетимо се да линеарно значи Θ ( n )). Слика 5 за дијаграм ће вам помоћи да разумете рекурзију када је позвано factorial(5). Ово би требало објаснити зашто је ова функција линеарне сложености.

Логаритамска сложеност[уреди | уреди извор]

**Слика 6:** Рекурзија позвана бинарном претрагом. Аргумент А у сваком позиву је означен црном. Рекурзија се наставља све док не у низу не остане један елемент.

Један познати проблем у рачунарству јесте проналажење вредности у низу. Ми смо раније решили овај проблем за општи случај. Овај проблем постаје занимљив ако имамо низ који је сортиран и желимо да пронађемо дату вредност унутар њега. Један начин да то урадимо зове се бинарна претрага. Гледамо елементе у средини нашег низа: Ако га нађемо тамо, завршили смо. У супротном, ако је вредност коју нађемо већа од вредности коју тражимо, знамо да ће онда наш елемент бити на левом делу низа. У супротном, знамо да ће бити на десном делу низа. Можемо делити те мање низове на пола док нам не остане један елемент за проверу. Тај метод употребом псеудокода:

def binarySearch( A, n, value ):
    if n = 1:
        if A[ 0 ] = value:
            return true
        else:
            return false
    if value < A[ n / 2 ]:
        return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value )
    else if value > A[ n / 2 ]:
        return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value )
    else:
        return true

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

Слика 6 ће вам помоћи да разумете како бинарна претрага функционише.

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

Сада ћемо покушати да анализирамо овај алгоритам. Опет, имамо рекурзивни алгоритам у овом случају. Претпоставимо, због једноставности, да се низ увек полови тачно на пола, игноришући сада + 1 и - 1 део у рекурзивном позиву. До сада би требало да будете уверени да мала промена, као што је игнорисање + 1 и - 1 неће утицати на наше резултате сложености. Претпоставимо да наш низ има величину која је тачно експонент од 2, због једноставности. Опет ова претпоставка не мења коначни резултат наше сложености до које ћемо доћи. Најгори случај за овај проблем ће се десити када се вредност коју тражимо не појављује уопште у нашем низу. У том случају, крећемо са низом величине n у први позив рекурзије, онда је низ величине n / 2 у следећем позиву. Онда ћемо добити низ величине n / 4 у наредном рекурзивном позиву, а затим низ величине n / 8 и тако даље. У принципу, наш низ је подељен на пола у сваком позиву, док не дођемо до 1. Дакле, хајде да напишемо број елемената у нашем низу за сваки позив:

0. итерација: n
1. итерација: n / 2
2. итерација: n / 4
3. итерација: n / 8
...
i. итерација: n / 2ⁱ
...
последња итерација: 1

Приметимо да у и-тој итерацији, наш низ има n / 2ⁱ елемената. То је зато што при свакој итерацији скраћујемо низ за пола, односно делимо број елемената за два. Ово множи именитељ са 2. Ако то урадимо i пута, добијамо n / 2ⁱ. Овај поступак се наставља и са свим већим i , те добијамо мањи број елемената док не стигнемо до последње итерације у којој имамо само 1 елемент. Ако желимо да нађемо i да сазнамо у којој итерацији ће остати, морамо да решимо следеће једначине:

1 = n / 2ⁱ

Ово ће бити само тачно ако смо стигли до последњег позива binarySearch() функције, не у општем случају. Па решавање за i ће нам помоћи у којој итерацији ће се рекурзија завршити. Множењем обе стране са 2ⁱ добијамо:

2ⁱ = n

Ове једначине би сада требало да вам буду познате ако из дела о логаритмима изнад. Решавањем за i имамо:

i = log( n )

Ово нам говори да је број итерација потребан да се уради бинарна претрага једнак log( n ) где је n број елемената у почетном низу.

На пример, узмимо да је n = 32, низ од 32 елемента. Колико пута ћемо га поделити на пола да добијемо само 1 елемент? Добијамо: 32 → 16 → 8 → 4 → 2 → 1. Поделили смо 5 пута, што и јесте логаритам од 32. Дакле, имамо да је сложеност бинарне претраге Θ( log( n ) ).

Последњи резултат нам дозвољава да поредимо бинарну са линеарног претрагом, нашом прошлом методом. Јасно је да како је log( n ) много мање од n, закључујемо да је бинарна претрага много бржи метод за претрагу елемента у низу од линеарне, па је препоручљиво да задржите низ сортираним ако планирате да вршите над њим много претраживања.

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

Оптимално сортирање[уреди | уреди извор]

Сада знате о анализирању сложености алгоритама, асимптотско понашање функција и велико О нотацију. Такође знате како да интуитивно разумете која је сложеност алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и тако даље. Знате симболе o, O, ω, Ω и Θ и шта анализа најгорег случаја значи.

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

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

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

def merge( A, B ):
    if empty( A ):
        return B
    if empty( B ):
        return A
    if A[ 0 ] < B[ 0 ]:
        return concat( A[ 0 ], merge( A[ 1...A_n ], B ) )
    else:
        return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) )

concat функција узима елемент, "главу", и низ, "реп", и враћа нови низ који садржи "главу" елемент као прву ствар у новом низу и дати "реп" елемент као остале елементе у низу. На пример, concat( 3, [ 4, 5, 6 ] ) враћа [ 3, 4, 5, 6 ]. Користимо A_n и B_n да означимо величине низа А и B, респективно.

Вежба 8

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

Анализом овог алгоритам откривамо да има покретно време Θ( n ), где је n дужина добијеног низа (n = A_n + B_n).

Вежба 9

Проверите да ли је покретно време спајања једнако Θ ( n ).

Користећи ову функцију можемо изградити бољи алгоритам за сортирање. Идеја је следећа: Делимо низ на два дела. Сортирамо сваки од два дела рекурзивно, онда спајамо два сортирана низа у један велики низ. У псеудокоду:

def mergeSort( A, n ):
    if n = 1:
        return A # it is already sorted
    middle = floor( n / 2 )
    leftHalf = A[ 1...middle ]
    rightHalf = A[ ( middle + 1 )...n ]
    return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) )

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

Вежба 10

Проверите исправност сортирања спајањем. То јест, проверите да ли је сортирање спајањем, како је дефинисано горе, стварно исправно сортира дати низ. Ако имате проблема са разумевањем како то ради, пробајте са малим примером низа и покрените га "ручно". Када покренете ову функцију ручно, уверите се да лева половина и десна половина буду оно што добијете када поделите низ приближно у средини; не мора тачно бити у средини ако низ има непаран број елемената (то је чему floor изнад служи).

Као последњи пример, анализирајмо сложеност сортирања спајањем. У сваком кораку сортирања спајањем, делимо низ у два дела једнаке величине, слично бинарној претрази. Међутим, у овом случају, ми одржавамо обе половине приликом извршења. Затим примењујемо алгоритам рекурзивно на сваку половину. Након рекурзивног враћања, примењујемо операцију спајања на резултат који је Θ( n ) времена .

Дакле, поделили смо оригинални низ у два низа величине n / 2 сваки. Онда смо спојили те низове, операција која спаја n елемената и на тај начин заузима Θ ( n ) времена.

Погледајте слику 7 да схватите ову рекурзију.

**Слика 7:** Рекурзивно дрво сортирања спајањем.

Да видимо шта се овде дешава. Сваки круг представља позив функцији mergeSort. Број написан у кругу указује на величину низа који се сортира. Плави круг на врху је оригинални позив mergeSort, где смо добили да сортирмо низ величине n. Стрелице показују рекурзивне позиве између функција. Почетни позив mergeSort чини два позива mergeSort на два низа, сваки величине n / 2. Ово указује на две стрелице на врху. Заузврат, сваки од ових позива чини два позива својим функцијама mergeSort на два низа величине n / 4 сваки, и тако даље док не стигне до низа величине 1. Овај дијаграм се зове рекурзивно дрво, јер илуструје како се рекурзија понаша и изгледа као дрво (корен је на врху, а листови су на дну, тако да у стварности то изгледа као обрнуто дрво).

Обратите пажњу да у сваком реду у горњем дијаграму, укупан број елемената је n. Да видите, погледајте сваки ред појединачно. Први ред садржи само један позив mergeSort са низом величине n, тако да је укупан број елемената n. Други ред има два позива mergeSort, сваки величине n / 2. Али n / 2 + n / 2 = n и тако поново, у овом низу укупан број елемената је n. У трећем реду, имамо 4 позива сваки од њих се примењује на n / 4-величине низа, укупан број елемената биће једнак n / 4 + n / 4 + n / 4 + n / 4 = 4n / 4 = n. Дакле, опет смо добили n елемената. Сада приметите да на сваком реду у овом дијаграму позивалац ће морати да изврши операцију спајања на елементима враћеним позивима. На пример, круг означен са црвеном бојом мора да сортира n / 2 елемента. Да би то урадио, дели n / 2 низ величине у два низа n / 4 величине, позива mergeSort рекурзивно да сортира оне (ови позиви су кругови означени зеленом бојом), а затим их спаја заједно. Ова операција спајања захтева да се споји n / 2 елемента. На сваком реду у нашем стаблу, укупан број спојених елемената је n. У реду који смо истражили, наша функција спаја n / 2 елемената и функције на њој десно (које су у плавој боји) такође има да споје n / 2 својих елемента. То даје n укупно елемената које треба спојити за ред који смо гледали.

По овом аргументу, сложеност за сваки ред је Θ( n ). Знамо да број редова у овом дијаграму, који се назива и дубина рекурзије дрвета, је log( n ). Разлог за то је потпуно исти као онај који смо користили приликом анализе сложеност бинарне претраге. Имамо log( n ) редова и сваки од њих је Θ( n ), тако да је сложеност mergeSort Θ( n * log( n ) ). Ово је много боље него Θ( n2 ) које нам сортирање избором даје (сетите се да је log( n ) много мање од n, и тако је n * log( n ) знатно мање од n * n = n²). Ако ово звучи компликовано за вас, не брините: није лако први пут кад видите. Поново посетите овај одељак и поново прочитајте о аргументима овде након што спроведете сортирање спајањем у вашем омиљеном програмском језику и потврдите да ради.

Као што сте видели у последњем примеру, анализа сложености омогућава нам да упоредимо алгоритме да видимо који је бољи. Под овим околностима, сада можемо бити прилично сигурни да ће сортирање спајањем надмашити сортирање избором за велике низове. Овај закључак би било тешко извући ако нисмо имали теоријску позадину анализе алгоритма коју смо развили. У пракси, заиста алгоритму сортирања је потребно времена Θ( n * log( n ) ). На пример, Линукс кернел користи алгоритам за сортирање по имену хипсорт, који има исто време рада као сортирање спајањем које је овде истражено, односно Θ( n log( n ) ) и тако да је оптималан. Приметите да нисмо доказали да су ови алгоритми за сортирање оптимални. То би захтевало мало више укључивања математичких аргумента, али будите сигурни да они не могу бити бољи са тачке гледишта сложености.

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

Литература[уреди | уреди извор]

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, MIT Press.
Dasgupta, Papadimitriou, Vazirani. Algorithms, McGraw-Hill Press.
Fotakis. Course of Discrete Mathematics at the National Technical University of Athens.
Fotakis. Course of Algorithms and Complexity at the National Technical University of Athens.

Мотивација[уреди | уреди извор]

Бројање инструкција[уреди | уреди извор]

Анализа најгорег случаја[уреди | уреди извор]

Асимптотско понашање[уреди | уреди извор]

Сложеност[уреди | уреди извор]

Велико О нотација[уреди | уреди извор]

Логаритми[уреди | уреди извор]

Рекурзивна сложеност[уреди | уреди извор]

Логаритамска сложеност[уреди | уреди извор]

Оптимално сортирање[уреди | уреди извор]

Литература[уреди | уреди извор]

Логаритми
[уреди | уреди извор]