Многи програмери који производе неке од најбољих и најкориснијих програма данас, као што су многе ствари које можемо видети или користити на интернету свакодневно, немају теоријску рачунарску основу. И поред тога, они су доста креативни, а ми смо им захвални за њихове програме.
Међутим, теорија рачунарства има своју сврху и принципе и може да се искористи да буде сасвим практичана. Овај чланак је намењен за програмере који знају свој посао, али немају теоријску основу. У чланку ће бити објашњени неки од највећих прагматичних алата раучунарских наука: Велико О нотација и анализа сложености алгоритма. Ови је алати су широко примењени у пракси, а након читања овог чланка, разумећете појмове као што су "велико О", "асимптотско понашање" и "анализа најгорег случаја".
Кроз овај чланку ћете наићи на разне савете који вас воде на занимљив садржај, често ван оквира теме о којој се дискутује. Ако сте индустријски програмер, врло је вероватно да сте већ упознати са већином ових концепата. Ако сте млађи ученик у програмирању, учествујете на такмичењима, ови савети ће вам дати назнаке о другим областима рачунарске науке или софтверског инжењерства које можда нисте још истражили и можете да их погледате да проширите своја интересовања.
Велико О нотација и анализа сложености алгоритма је нешто што је многим индустријским програмерима и ученицима подједнако тешко да схвате, или избегавају као бескорисно. Али то није тако тешко или теоријско као што можда изгледа на први поглед. Сложеност алгоритма је само начин да се формално измери колико брзо програм или алгоритам ради, тако да је заиста прагматичано.
Почнимо са мало мотивисања теме.
Мотивација
Већ знамо да постоје програми за мерење брзине извршавања програма. Ти програми се називају профајлери и мере потребно време извршавања у милисекундама, те нам помажу при оптимизацији кода. Иако је ово средство корисно, није баш важно за алгоритамску сложеност. Сложеност алгоритма је нешто креирано за поређење два алгоритма на нивоу идеје - игнорисањем детаља ниског нивоа, као што је имплементација програмског језика, хардвера на коме се алгоритам покреће или скупа инструкција датог процесора. Циљ је да се упореди алгоритам у његовом смислу: Идеје како се израчунава тако нешто. Бројање милисекунди неће нам помоћи у томе. Сасвим је могуће да лош алгоритам написан у програмском језику ниског нивоа као што је асемблер ради много брже него добар алгоритам написан у језику високог нивоа као што су Пајтон или Руби. Тако да је време да се дефинише шта "бољи алгоритам" заиста јесте.
Алгоритми су програми који обављају само рачунање, а не друге ствари које рачунари често раде, као што су умрежавање задатака или кориснички унос и приказ. Анализа сложености омогућава да се измери колико је брз програм када се обавља израчунавање. Примери операција које су чисто рачунске и укључују нумеричке операције са децималним бројевима, као што сабирање и множење; претраживање базе података која се уклапа у РАМ за дате вредности; одређивање путање лика са вештачком интелигенцијом којом ће ходати у видео игрици, тако да пређе кратко растојање у свом виртуелном свету (види слику 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 тежи бесконачности. (Узгред, у строгом математичком окружењу, ми не би могли да одбацимо константу у лимиту, али за рачунарске потребе науке, радимо то из разлога који је горе наведен.)
Пронађимо асимптотско понашање на примерима функција одбацивањем константи и задржавањем услова најбржег раста. thumb|479x479px|Слика 2: n3 функција, нацртана плавом, постаје већа него 1999n функција, нацртана црвеном, после n = 45. После те тачке остаје већа заувек. f( n ) = 5n + 12 даје f( n ) = n. Разлог је наведен горе. f( n ) = 109 даје f( n ) = 1. Одбацујемо множење 109 * 1, али остављамо 1 овде да укажемо на то да ова функција има не-нултну вредност f( n ) = n2 + 3n + 112 даје f( n ) = n2Овде, n2 расте брже од n за довољно велико n, па узимамо то.