Algoritamska složenost

Mnogi programeri koji proizvode neke od najboljih i najkorisnijih programa danas, kao što su mnoge stvari koje možemo videti ili koristiti na internetu svakodnevno, nemaju teorijsku računarsku osnovu. I pored toga, oni su dosta kreativni, a mi smo im zahvalni za njihove programe.

Međutim, teorija računarstva ima svoju svrhu i principe i može da se iskoristi da bude sasvim praktičana. Ovaj članak je namenjen za programere koji znaju svoj posao, ali nemaju teorijsku osnovu. U članku će biti objašnjeni neki od najvećih pragmatičnih alata raučunarskih nauka: Veliko O notacija i analiza složenosti algoritma. Ovi je alati su široko primenjeni u praksi, a nakon čitanja ovog članka, razumećete pojmove kao što su "veliko O", "asimptotsko ponašanje" i "analiza najgoreg slučaja".

Kroz ovaj članku ćete naići na razne savete koji vas vode na zanimljiv sadržaj, često van okvira teme o kojoj se diskutuje. Ako ste industrijski programer, vrlo je verovatno da ste već upoznati sa većinom ovih koncepata. Ako ste mlađi učenik u programiranju, učestvujete na takmičenjima, ovi saveti će vam dati naznake o drugim oblastima računarske nauke ili softverskog inženjerstva koje možda niste još istražili i možete da ih pogledate da proširite svoja interesovanja.

Veliko O notacija i analiza složenosti algoritma je nešto što je mnogim industrijskim programerima i učenicima podjednako teško da shvate, ili izbegavaju kao beskorisno. Ali to nije tako teško ili teorijsko kao što možda izgleda na prvi pogled. Složenost algoritma je samo način da se formalno izmeri koliko brzo program ili algoritam radi, tako da je zaista pragmatičano.

Počnimo sa malo motivisanja teme.

Motivacija

Već znamo da postoje programi za merenje brzine izvršavanja programa. Ti programi se nazivaju profajleri i mere potrebno vreme izvršavanja u milisekundama, te nam pomažu pri optimizaciji koda. Iako je ovo sredstvo korisno, nije baš važno za algoritamsku složenost. Složenost algoritma je nešto kreirano za poređenje dva algoritma na nivou ideje - ignorisanjem detalja niskog nivoa, kao što je implementacija programskog jezika, hardvera na kome se algoritam pokreće ili skupa instrukcija datog procesora. Cilj je  da se uporedi algoritam u njegovom smislu: Ideje kako se izračunava tako nešto. Brojanje milisekundi neće nam pomoći u tome. Sasvim je moguće da loš algoritam napisan u programskom jeziku niskog nivoa kao što je asembler radi mnogo brže nego dobar algoritam napisan u jeziku visokog nivoa kao što su Pajton ili Rubi. Tako da je vreme da se definiše šta "bolji algoritam" zaista jeste.

Algoritmi su programi koji obavljaju samo računanje, a ne druge stvari koje računari često rade, kao što su umrežavanje zadataka ili korisnički unos i prikaz. Analiza složenosti omogućava da se izmeri koliko je brz program kada se obavlja izračunavanje. Primeri operacija koje su čisto računske i uključuju numeričke operacije sa decimalnim brojevima, kao što sabiranje i množenje; pretraživanje baze podataka koja se uklapa u RAM za date vrednosti; određivanje putanje lika sa veštačkom inteligencijom kojom će hodati u video igrici, tako da pređe kratko rastojanje u svom virtuelnom svetu (vidi sliku 1); ili pretraga regularnog izraza u nizu. Jasno, računanje je sveprisutno u računarskim programima.

Analiza složenosti je takođe alat koji objašnjava kako se algoritam ponaša kada unos raste. Ako ubacujemo različite unose, kako će se ponašati algoritam? Ako našem algoritmu treba 1 sekunda da završi za unos veličine 1000, kako će se ponašatu ako se udvostruči veličina unosa? Da li će se pokrenuti istom brzinom, pola od te brzine, ili četiri puta sporije? U praktičnom programiranju, ovo je važno jer nam omogućava da predvidimo kako će se ponašati naš algoritam kada unos podataka postaje sve veći. Na primer, ako smo napravili algoritam za veb aplikaciju koja radi dobro sa 1000 korisnika i meri svoje vreme rada, koristeći analizu složenosti algoritma imaćemo prilično dobru predstavu o tome šta će se desiti kada se broj budeo popeo na 2000 korisnika. Za algoritamska takmičenja, analiza složenosti nam daje uvid o tome koliko dugo će se naš kod izvršavati za najveće testirane vrednosti koje služe za testiranje ispravnost našeg programa. Dakle, ako merimo ponašanje našeg programa za mali unos, možemo dobiti dobru ideju kako će se ponašati za veće unose. Počnimo od jednostavnog primera: Pronalaženje maksimalnog elementa u nizu.

Brojanje instrukcija

U ovom članku ću koristiti različite programske jezike za primere. Međutim, ne očajavajte ako ne znate određeni programski jezik. Pošto znate programiranje, trebalo bi da možete da pročitate primere bez ikakvih problema čak i ako niste upoznati sa izabranim programskim jezikom, jer je kod jednostavan i neće se koristiti dodatne funkcije specifične za taj jezik.

Maksimalni element u nizu može se potražiti pomoću jednostavnog koda kao što je ovaj javaskript kod. Dat je ulaz niza A veličine n:

var M = A[ 0 ];

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

Sada, prva stvar koju ćemo uraditi je da izbrojimo

koliko osnovnih instrukcija taj deo koda izvršava. Mi ćemo to učiniti samo jednom i to neće biti potrebno kako budemo razvijali teoriju. Za analiziranje ovog koda, podelićemo ga na manje delove; stvari koje može procesor direktno da izvršava - ili barem blizu tome. Pretpostavićemo da naš procesor može izvršiti sledeće operacije kao jedna instrukcija za svaku:

• dodelu vrednosti promenljivoj
• pretragu vrednosti određenog  elementa u nizu
• poređenje dve vrednosti
• inkrementiranje vrednosti
• osnovne aritmetičke operacije kao što su sabiranje i množenje

Pretpostavimo da se grananje (izbor između „if" i „else" delova koda posle

izračunavanja „if") javlja odmah i nećemo računati ovu instrukciju. U gornjem kodu, prva linija koda je:

var M = A[ 0 ];

Ovo zahteva 2 instrukcije: jedna za pretragu A[ 0 ] i druga za dodeljivanje vrednosti M ( pod pretpostavkom da je n uvek barem 1). Ove dve instrukcije su uvek zahtevane od algoritma, bez obzira na vrednost n. Početni kod „for" petlje takođe mora da uvek radi. To nam daje još dve instrukcije: dodelu i poređenje:

i = 0;
i < n;

Ovo će se pokrenuti pre prvog prolaska kroz „for" petlju. Nakon svake iteracije petlje, imamo još dve instrukcije za pokretanje: povećanje i i provera da li ćemo ostati u petlji:

++i;
i < n;

Dakle, ako zanemarimo telo petlje, broj instrukcija ovog algoritma je 4 + 2n.

To je, 4 instrukcije na početku petlje i 2 instrukcije na kraju svake iteracije kojih imamo n. Sada možemo definisati matematičku funkciju f( n ) tako da za dato n vraća broj instrukcija potrebnih algoritmu.

Za prazno telo petlje, imamo f( n ) = 2n + 4.

Analiza najgoreg slučaja

Sada, gledajući telo petlje, imamo operaciju pretrage niza i poređenje koje se uvek izvršava:

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

To su dve instrukcije. Ali, „if" telo se može pokrenuti, ali i ne mora, zavisno od toga koje su vrednosti niza. Ako se desi da je A[ i ] >= M, onda ćemo pokrenuti ove dve dodatne instrukcije - pretragu niza i dodelu:

M = A[ i ];

Ali sada ne možemo definisati  f( n ) tako lako, jer naš broj instrukcija ne zavisi samo od n, već i od našeg ulaza. Na primer, za  A = [ 1, 2, 3, 4 ] algoritmu je potrebno više instrukcija nego za  A = [ 4, 3, 2, 1 ]. Prilikom analize algoritma, često u razmatranje uzimamo najgori slučaj. Šta je najgore što se može desiti za algoritam? Kada našem algoritam treba najviše instrukcija da se završi? U ovom slučaju, to je kada imamo niz u rastućem redosledu, kao što je A = [ 1, 2, 3, 4 ]. U tom slučaju, M treba da se zameni svaki put i to daje najviše instrukcija. Računarski naučnici imaju fensi ime za to i oni ga nazivaju analiza najgoreg slučaja; to je ništa više nego da uzimamo u obzir slučaj kada imamo najmanje sreće. Dakle, u najgorem slučaju, imamo 4 instrukcije unutar tela petlje, tako da imamo f( n ) = 4 + 2n + 4n = 6n + 4. Ova funkcija f, u zavisnosti od veličine problema n, daje nam broj instrukcija koje će biti potrebne u najgorem slučaju.

Asimptotsko ponašanje

S obzirom na takvu funkciju, imamo prilično dobru ideju o tome koliko je brz algoritam. Međutim, neće biti potrebe da prođemo kroz težak zadatak brojanja instrukcija u našem programu. Osim toga, broj stvarno potrebnih procesorskih instrukcija za svaku izjavu programskog jezika zavisi od prevodioca našeg programskog jezika i od dostupnih performansi procesora (odnosno da li je AMD ili Intel Pentium na računaru, ili MIPS procesor na Plejstejšnu 2), a to ćemo da ignorišemo. Sada ćemo pokrenuti našu "f" funkciju kroz "filter" koji će pomoći da se otarasimo onih manjih detalja koje računarski naučnici vole da ignorišu.

U našoj funkciji, 6n + 4, imamo dva uslova: 6n i 4. U analizi složenosti zanima nas samo šta se dešava sa funkcijom brojanja instrukcija za povećane ulaza programa ( n ). Ovo stvarno ide zajedno sa prethodnim idejama ponašanja "najgoreg slučaja": zanima nas kako se naš algoritam ponaša u težim slučajevima; kada je izazvan da uradi nešto teže. Obratite pažnju da je ovo zaista korisno da se uporede algoritami. Ako algoritam pobedi drugi algoritam za veliki ulaz, verovatno je da brži algoritam ostaje brži za manje unose. Iz uslova koje posmatramo, odbacićemo sve uslove koji sporije rastu i zadržataćemo se samo na one koji rastu brzo kako n postaje sve veći. Jasno je da 4 ostaje 4 kako n raste, ali 6n se povećava sve više i više, tako da teži da vredi više i više za veće probleme. Dakle, prva stvar koju ćemo uraditi je da odbacimo 4 i uzmemo funkciju  f( n ) = 6n.

To ima smisla, ako razmislite o tome, jer je 4 "konstanta za inicijalizaciju". Različitim programskim jezicima treba različito vreme da se pokrenu. Na primer, Javi treba neko vreme da pokrene svoju virtuelnu mašinu. Pošto ignorišemo razlike u programskim jezicima, možemo ignorisati i ovu vrednost.

Druga stvar koju ćemo ignorisati je konstanta množenja ispred n, pa će naša funkcija sada biti f( n ) = n. Kao što možete videti ovo pojednostavljuje

stvari dosta. Opet, ima smisla da konstantu množenja odbacimo ako razmišljamo o tome kako različiti programski jezici prevode. "Pretraživanje niza" instrukcija na jednom jeziku može se prevesti na različite instrukcije u drugom programskom jeziku. Na primer, u C, A[ i ] ne obuhvata proveru da je i u deklarisanoj veličini niza, dok u Paskalu to radi. Dakle, sledeći kod u paskalu:

M := A[ i ]

i njemu ekvivalentan kod u C-u:

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

Razumno je očekivati da će različiti programski jezici imati različite faktore kada računamo njihove instrukcije. U našem primeru u kojem smo koristili loš kompajler za Paskal, jasno je da je moguća optimizacija, Paskal zahteva 3 instrukcije za svaki pristup nizu umesto 1 instrukcije koju C zahteva. Izostavljanje ovog faktora ide sa ignorisanjem razlike između pojedinih programskih jezika i kompajlera i ostaje samo analiza ideje samog algoritma.

Ovaj filter  "ignorisanja svih faktora" i "zadržavanja najvećeg rastućeg uslova" kako je gore opisano je ono što zovemo asimptotsko ponašanje. Dakle, asimptotsko ponašanje f( n ) = 2n + 8 je  funkcija f( n ) = n. Matematički gledano, kažemo da nas zanima limit funkcije f kako n teži beskonačnosti. (Uzgred, u strogom matematičkom okruženju, mi ne bi mogli da odbacimo konstantu u limitu, ali za računarske potrebe nauke, radimo to iz razloga koji je gore naveden.)

Pronađimo asimptotsko ponašanje na primerima funkcija odbacivanjem konstanti i zadržavanjem uslova najbržeg rasta.

Slika 2: n³ funkcija, nacrtana plavom, postaje veća nego 1999n funkcija, nacrtana crvenom, posle n = 45. Posle te tačke ostaje veća zauvek.

1. f( n ) = 5n + 12 daje f( n ) = n. Razlog je naveden gore.  
2. f( n ) = 109 daje f( n ) = 1. Odbacujemo množenje 109 * 1, ali ostavljamo 1 ovde da ukažemo na to da ova funkcija ima ne-nultnu vrednost
3. f( n ) = n² + 3n + 112 daje f( n ) = n²Ovde, n² raste brže od n za dovoljno veliko n, pa uzimamo to.
4. f( n ) = n³ + 1999n + 1337 daje f( n ) = n³Iako je faktor ispred n prilično veliki, još uvek možemo naći dovoljno veliko  n, tako da je n³veće od 1999n. Kako smo zainteresovani za ponašanje za veoma velike vrednosti n, uzimamo samo n³ (vidi sliku 2).
5. f( n ) = n +${\textstyle {\sqrt {n}}}$ daje f( n ) = n To je zato što n raste brže od ${\textstyle {\sqrt {n}}}$ kako povećavamo n.

Možete isprobati sledeće primere:

Vežba 1

1. f( n ) = n⁶ + 3n
2. f( n ) = 2ⁿ + 12
3. f( n ) = 3ⁿ + 2ⁿ
4. f( n ) = nⁿ + n

Ako imate problema sa nekim zadatkom gore, koristite neko veliko n i uporedite rezultate.

Složenost

Pošto ignorišemo sve ove dekorativne konstante, postaje prilično lako predvideti asimptotsko ponašanje funkcije brojanja instrukcija programa. U stvari, svaki program koji nema petlju će imati  f( n ) = 1, jer je broj potrebnih instrukcija samo konstanta (osim ako se koristi rekurziju; vidi dole). Bilo koji program sa jednom petljom koja ide od 1 do n imaće f( n ) = n, jer će biti konstantan broj instrukcija pre petlje, konstantan broj instrukcija posle petlje, i konstantan broj instrukcija unutar petlje koja se pokreće n puta.

Ovo bi sada moglo biti mnogo lakše i manje naporno od brojanja pojedinačnih instrukcija, pa hajde da

pogledamo nekoliko primera da se upoznamo sa ovim. Sledeći PHP program proverava da li određena vrednost postoji u okviru niza A veličine n:

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

Ovaj metod pretraživanja vrednosti u nizu zove se linearna pretraga.

Ovo je razumno ime, jer ovaj program ima f( n ) = n ( definicija šta "linearno" znači je u sledećem odeljku). Možete primetiti da postoji "break" izjava ovde koja može da ranije prekine program, čak i posle jednog ponavljanja. Ali kako nas zanima najgori slučaj, odnosno u ovom slučaju je to da se u nizu A ne nalazi vrednost. Dakle, još uvek imamo f( n ) = n.

Vežba 2

Sistematski analizirajte broja instrukcija gornjeg PHP programa, treba u odnosu na n u najgorem slučaju da bude f( n ), slično kako smo analizirali naš prvi javaskript program. Zatim proverite to, da, asimptotski imamo f( n ) = n.

Pogledajmo Pajton program koji sabira dva elemenata niza i daje zbir te dve promenljive u novu promenljivu:

v = a[ 0 ] + a[ 1 ]

Ovde imamo konstantan broj instrukcija, tako da imamo f( n ) = 1. Sledeći program u C++ proverava da li vektor (fensi niz) pod nazivom A veličine n sadrži iste dve vrednosti bilo gde u njemu (duplikate):

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;
   }
}

Kako ovde imamo dve ugnježdene petlje, jedna unutar druge, imaćemo asimptotsko ponašanje opisano sa f( n ) = n²

Pravilo:

Jednostavni programi mogu se analizirati brojanjem ugnježdenih petlji u

programu. Jedna petlja od n elemenata daje  f( n ) = n. Petlja u okviru

petlje prinosi  f( n ) = n². Petlja u petlji u okviru petlje prinosi f( n ) = n³.

Ako imamo program koji poziva funkciju u okviru petlje i znamo broj instrukcija koje pozvana funkcija obavlja, lako je utvrditi broj instrukcija celog programa. Zaista, hajde da pogledamo ovaj C primer:

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

Ako znamo da je f( n )  funkcija koja obavlja tačno n instrukcija, onda možemo znati da je broj instrukcija čitavog programa  asimptotski n², kako je funkcija tačno n puta zvana.

Pravilo:

Za datu seriju petlji koje su u nizu, najsporija od njih određuje asimptotsko ponašanje programa. Dve ugnežđene petlje praćene jednom petljom su asimptotski iste kao ugnježdene petlje same, jer ugnježdene petlje

dominiraju u odnosu na jednostavnu petlju.

Kada smo shvatili šta je  f asimptotski, reći ćemo da je naš program Θ( f( n ) ).

Na primer, navedeni programi su Θ( 1 ), Θ( n2 ) i Θ( n² )  respektivno.  Θ( n ) se izgovara "teta od n". Ponekad možemo reći da je f( n ), originalna funkcija brojenja instrukcija, uključujući konstante, je Θ (nešto). Na primer, možemo reći da je  f( n ) = 2n  funkcija koja je Θ( n ) - ništa novo ovde. Takođe možemo zapisati 2n ∈ Θ( n ), koji se izgovara kao "dva n pripada teta od n". Sve što notacija govori je da ako smo računali broj potrebnih instrukcija programa  i on je 2n, onda asimptotsko ponašanje našeg algoritma je opisano sa n, koje smo našli izostavljanjem konstante . Sa ovom notacijom date su neke prave matematičke izjave:

1. n⁶ + 3n ∈ Θ( n⁶ )
2. 2ⁿ + 12 ∈ Θ( 2ⁿ )
3. 3ⁿ + 2ⁿ ∈ Θ( 3ⁿ )
4. nⁿ + n ∈ Θ( nⁿ )

Uzgred, ako ste rešili vežbu 1 gore, ovo su upravo odgovori koje je trebalo da dobijete.

Ovu funkciju nazivamo, odnosno ono što smo stavili Θ(ovde), vremenska složenost ili samo složenost našeg algoritma. Dakle algoritam sa Θ (n) je složenosti n. Takođe imamo posebne nazive za Θ (1), Θ (n), Θ ( n² ) i Θ( log( n ) ), jer se pojavljuju vrlo često. Kažemo da je Θ (1)

algoritam konstantno-vremenski algoritam, Θ ( n ) je linearni, Θ ( n² ) je kvadratni i Θ( log( n ) ) je logaritamski.

Pravilo: Program sa većim Θ radi sporije nego program sa manjim Θ.

Veliko O notacija

Sada, ponekad će biti teško da razumemo tačno ponašanje algoritma na ovaj način kao što smo gore uradili, posebno za složenije primere. Međutim, možemo da kažemo da ponašanje našeg algoritma nikada neće preći određene granice. To će učiniti život lakšim za nas, jer nećemo morati da odredimo tačno koliko brzo naš algoritam radi, čak i kada ignorišemo konstante onako kako smo ih ranije ignorisali. Sve što treba da se uradi je da se nađe određena granica. Ovo je lako objasniti jednim primerom.

Poznati problem koji računarski naučnici koriste za učenje algoritama je problem sortiranja. U problemu sortiranja, niz A veličine n je dat (zvuči poznato?) i traži se da napišemo program koji sortira ovaj niz. Ovaj problem je interesantan jer je pragmatičan problem u realnim sistemima. Na primer, čitač dokumenata treba da sortira fajlove po imenu, tako da korisnik može lako da se snalazi među njima. Ili, kao drugi primer, u video igri može biti potrebno sortiranje 3D objekata prikazanih u svetu na osnovu njihove udaljenosti od oka igrača unutar virtuelnog sveta kako bi se utvrdilo šta je vidljivo, a šta nije, nešto što se zove problem vidljivosti (vidi sliku 3). Predmeti koji se ispostave da su najbliži igraču su oni vidljivi, dok oni dalji mogu dobiti skriveni predmeti. Sortiranje je takođe interesantno jer postoje mnogi algoritmi koji ga rešavaju, od kojih su neki gori od drugih. Takođe je jednostavan problem definisati i

objasniti. Dakle, hajde da napišemo kod koji sortira niz. Ovde je neefikasan način da se sprovede sortiranje niz u Rubiju. (Naravno, Rubi podržava sortiranje nizova pomoću ugrađenih funkcija koje bi trebalo umesto toga da koristite, a koje su svakako brže nego što ćemo videti ovde. Ali ovo je ovde radi ilustracije.)

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

Ovaj metod se naziva sortiranje izborom. On nalazi minimum našeg niza (niz je označaen gore, dok je minimalna vrednost označena sa m, a mi je njen indeks), stavlja ga na kraj novog niza (u našem slučaju b),

i uklanja ga iz originalnog niza. Onda pronalazi minimum između ostalih vrednosti našeg originalnog niza, dodaje ja u naš nov niz tako da on sada sadrži dva elementa, i uklanja ga iz našeg originalnog niza. Nastavlja ovaj proces dok svi predmeti ne budu uklonjeni iz originalnog niza i ubačeni u novi nizu što znači da je niz je sortiran. U ovom primeru, vidimo da imamo dve ugnježdene petlje. Spoljna petlja radi n puta, a unutrašnja petlja radi jednom za svaki element niza a. Dok niz a prvobitno ima n elemenata, uklanjamo po jedan element u svakoj iteraciji. Tako da se unutrašnja petlja ponavlja n puta tokom prve iteracije spoljašnje petlje, a zatim n - 1 puta, onda n - 2 puta i tako dalje, do poslednjeg ponavljanja spoljašnje petlje tokom koje radi samo jednom.

Malo je teže proceniti složenost ovog programa, kao što smo morali da pronađemo zbir 1 + 2 + ... + (n - 1) + n. Ali možemo sa sigurnošću znati "gornju granicu" za njega. To jest, možemo menjati naš program da bude gori nego što jeste, a onda naći složenost tog novog programa koji smo izveli. Ako možemo naći složenost goreg programa koji smo izgradili, onda znamo da je naš originalni program najviše toliko loš, ili možda bolji. Na taj način, ako nađemo prilično dobru složenost za naš izmenjen program, koji je gori nego originalni, možemo znamo da će naš originalan program imati prilično dobru složenost- bilo dobar kao naš izmenjeni program ili još bolji.

Nađimo način da izmenimo primer programa da bi lakše došli do njegove složenosti. Ali imajmo na umu da možemo samo pogoršati, odnosno učiniti ga sa više instrukcija, tako da je naša procena značajna za naš originalan program.Jasno je da možemo menjati unutrašnju petlju programa da se uvek ponavlja tačno n puta umesto različitog broj puta. Neka od ovih ponavljanja će biti beskorisna, ali to će nam pomoći pri analizi složenosti rezultujućeg algoritma. Ako napravimo ovu jednostavnu promenu, onda je novi algoritam koji smo izgradili Θ( n² ), jer imamo dve ugnježdene petlje gde se svaka ponavlja tačno n puta. Ako je tako, kažemo da je originalni algoritam O( n² ).  O( n² ) se izgovara "veliko O od n na kvadrat". Ovo govori da naš program  asimptotski nije gori nego n². Može biti bolji od toga, ili može biti isti kao to. Uzgred, ako je naš program zaista Θ( n² ), možemo dalje tvrditi da je O( n² ). Da shvatite to da, zamislite menjanje originalnog programa na način na koji to ne menja mnogo, ali ipak čini malo gore, kao što je dodavanje besmislene instrukcije na početku programa. Ovako će se promeniti funkcija brojanja instrukcija prostom konstantom, koja se ignoriše kada je u pitanju asimptotsko ponašanje. Dakle, program koji je Θ( n² ) je takođe O( n² ). Ali program koji je O( n² ) ne mora biti i Θ ( n² ). Na primer, bilo program koji je Θ ( n ) je takođe O ( n² ) pored toga što O ( n ). Ako zamislimo da Θ( n ) program je jednostavna petlja koja se ponavlja n puta, a možemo napraviti gore tako što ćemo je ugnezditi u drugu petlju koja se ponavlja n puta, i na taj način proizvodeći program sa f( n ) = n². Da bi to generalizovali, svaki program koji je Θ( a ) je O( b ) kada je b gore nego a. Obratite pažnju da naša promena u programu ne mora da nam vrati program koji je zapravo smislen ili ekvivalentan našem originalnom programu. Već samo treba da obavi više instrukcija nego originalni za dato n. Sve što koristimo za brojanje instrukcija, zapravo nije rešenje našeg problema.

Dakle, rekavši da je naš program O( n² ) bio na sigurnoj strani: Analizirali smo naš algoritam, i otkrili da nikada neće biti gori od n². Ali, moguće je da je to, u stvari, n². To nam daje dobru procenu koliko brzo naš program radi. Sledi nekoliko primera da vam pomogne da se upoznate sa ovim novim oznakama.

Vežba 3

Naći koja je od sledećih izjava tačna:

1. A Θ( n ) algoritam je O( n )
2. A Θ( n ) algoritam je O( n² )
3. A Θ( n² ) algoritam je O( n³ )
4. A Θ( n ) algoritam je O( 1 )
5. A O( 1 ) algoritam je Θ( 1 )
6. A O( n ) algoritam je Θ( 1 )

Rešenje

1. Znamo da je tačno kao što je naš originalan program bio Θ( n ). Možemo postići O( n ) bez ikakve izmene našeg programa.
2. Kako je n² gore nego n, ovo je tačno.
3. Kako n³ gore nego n², ovo je tačno.
4. Kako1 nije gore od n, ovo je netačno. Ako programu treba n instrukcijaasimptotski (linearan broj instrukcija), ne možemo učiniti gore i imatisamo 1 instrukciju asimptotski (konstantan broj instrukcija).
5. Ovo je tačno kako su dve složenosti jednake.
6. Ovomože, a i ne mora biti tačno u zavisnosti od algoritma. U opštemslučaju je netačno. Ako je algoritam Θ( 1 ), onda je jasno O( n ). Aliako je O( n ) onda ne mora biti Θ( 1 ). Na primer, Θ( n ) algoritam jeO( n ) ali nije Θ( 1 ).

Vežba 4

Koristiteći sumu aritmetičke progresije dokazati da  program iznad nije samo O( n² ), nego i Θ ( n² ). Pošto O-složenost algoritma daje gornju granicu za stvarne složenosti algoritma, dok Θ daje stvarnu složenost algoritma, ponekad kažemo da nam Θ daje čvrstu granicu. Ako znamo da složenost granice koja nije čvrsta, takođe možemo koristiti malo o da označimo to. Na primer, ako je algoritam Θ( n ), onda je čvrsta složenost n. Onda je ovaj algoritam i O( n ) i O( n² ). Pošto je algoritam Θ( n ), O( n ) je čvrsta granica. Ali O( n² ) ako nije vezano čvrsto, onda možemo napisati da je algoritam o( n2 ), što se izgovara "malo o od n na kvadrat" da ilustruje da naša veza nije čvrsta. To je bolje ako možemo da pronađemo čvrste granice za naš algoritam, kako nam daje više informacija o tome kako se naš algoritam ponaša, ali to nije uvek lako uraditi.

Vežba 5

Odredite koje od sledećih granica su čvrste granice i koji nisu čvrste granice. Proverite da li granice mogu da budu pogrešne. Koristite o (notaciju) da ilustrujete granice koje nisu čvrste.

1. A Θ( n ) je algoritam za koji smo našli da je O( n ) gornja granica.
2. A Θ( n² ) je algoritam za koji smo našli da je O( n³ ) gornja granica.
3. A Θ( 1 ) je algoritam za koji smo našli da je O( n ) gornja granica.
4. A Θ( n ) je algoritam za koji smo našli da je O( 1 ) gornja granica.
5. A Θ( n ) je algoritam za koji smo našli da je O( 2n ) gornja granica.

Rešenje

1. U tom slučaju, složenost Θ i složenost O su isti, tako da granica čvrsta.
2. Ovde vidimo da je složenost O  većih razmera nego složenost Θ tako da granica nije čvrsta. Zaista, granica za O( n² ) će biti čvrsta. Tako možemo napisati da je algoritam o( n³ ).
3. Opetvidimo da složenost O većih razmera nego složenost Θ tako da imamogranicu koja nije čvrsta. Granica za O (1) će biti čvrsto jedan. Dakle, možemo istaći da granica O( n ) nije čvrsta zapisivanjm o( n ) .
4. Morada smo napravili grešku u obračunu ove granice, jer je pogrešno. Nemoguće je za  Θ( n ) algoritam da ima gornju granicu O (1), kako je n veća složenost od 1. Zapamtite da O daje gornju granicu.
5. Tomože izgledati kao granica koja nije čvrsta, ali to nije istina. Ovagranice je u stvari čvrsta. Podsetimo da je asimptotsko ponašanje 2n i nisto, a to O i Θ su samo zabrinuti sa asimptotskim ponašanjem. Tako imamoda je O( 2n ) = O( n ) i stoga je ovo granica je čvrsta kako jekompleksnost ista kao i Θ.

Pravilo: Lakše je razumeti O složenot algoritma nego Θ složenost

Notacije koje smo koristili do sada Θ, O i o, nam više neće koristiti u ovom članku, jer u uvodimo nove dve. U gornjem primeru, izmenili smo naš program da bi ga napravili još gorim (tj. uzimanje više instrukcija i samim tim on zahteva više vremena) i stvorili O notaciju. O je smisleno, jer nam govori da naš program nikada neće biti sporiji od specifične granice, tako da pruža vredne informacije, odakle zaključujemo valjanost našeg programa. Ako uradimo suprotno i izmenimo naš program da bude bolji i nađemo složenost rezultujućeg programa, koristićemo notaciju Ω. Ω nam stoga daje složenost gde znamo da naš program neće biti bolji. Ovo je korisno ako želimo da dokažemo da program radi sporo ili je algoritam

loš. Ovo može biti takođe korisno da se utvrdi da je algoritam prespor za upotrebu u konkretnom slučaju. Na primer, ako se kaže da je algoritam je Ω( n³ ) to znači da algoritam nije bolji od n³. Može biti Θ( n³ ), loš kao Θ( n⁴ ) ili još gori, ali znamo da je bar donekle nešto loše. Tako nam Ω daje donju granicu za složenost našeg algoritma. Slično kao ο, možemo zapisati ω ako znamo da naša granica nije čvrsta. Na primer, Θ( n³ ) algoritam je ο( n⁴ ) i ω( n² ). Ω( n ) se čita "veliko omega od n", dok se ω (n) izgovara "malo omega od n"

Vežba 6

Za Θ složenost napišite čvrstu i ne-čvrstu O granicu, i čvrstu i ne-čvrstu Ω granicu po vašem izboru, pod uslovom da postoje.

1. Θ( 1 )
2. Θ( ${\textstyle {\sqrt {n}}}$ )
3. Θ( n )
4. Θ( n² )
5. Θ( n³ )

Rešenje

Ovo je pravolinijska primena gore navedenih definicija.

1. Čvrsta granica će biti O (1) i Ω (1). Ne-čvrsta O-granica biće O (n ). Podsetimo se da nam O daje gornju granicu. Kako je nvećeg obima od 1 ovo je ne-čvrsta granica i možemo je zapisati kao o( n). Ali ne možemo da nađemo ne-čvrstu granicu za Ω, jer ne možemo dobitimanje od 1 za ove funkcije. Dakle, moraćemo da radimo sa čvrstomgranicom.
2. Čvrsta granica će morati da bude ista kao složenost Θ, tako da je O( ${\textstyle {\sqrt {n}}}$ ) i Ω( ${\textstyle {\sqrt {n}}}$ ), respektivno. Za ne-čvrstu granicu možemo imati O( n ), kako je n veće od ${\textstyle {\sqrt {n}}}$ tako da je gornja granica za ${\textstyle {\sqrt {n}}}$. Kao što znamo ova ne-čvrsta gornja granica se može zapisati i kao o( n). Za donju granicu koja nije čvrsta, možemo jednostavno koristiti Ω( 1). Kao što znamo da ta granica nije čvrsta, možemo zapisati kao  ω( 1 ).
3. Čvrstegranice su O( n ) i Ω( n ). Dve ne-čvrste  granice mogu biti ω( 1 ) io( n3 ). To su u stvari prilično loše granice, jer su daleko odoriginalnih složenosti, ali i dalje važe po našim definicijama.
4. Čvrste granice su O( n2 ) i Ω( n2 ). Za ne-čvrste granice smo opet mogli koristiti ω( 1 ) i o( n³ ) kao u našem prethodnom primeru.
5. Čvrste granice su O( n³ ) i Ω( n³ ) respektivno. Dve ne-čvrste granice mogu biti ω( ${\textstyle {\sqrt {n}}}$ n² ) i o( ${\textstyle {\sqrt {n}}}$ n³ ). Iako ove granice nisu bliske, bolje su od onih koje smo gore naveli.

Razlog zašto koristimo O i Ω umesto Θ iako O i Ω mogu dati čvrste granice je da možda nećemo moći da kažemo da li je granica čvrsta, ili jednostavno ne želimo da prođemo kroz proces tolikog preispitivanja. Najvažniji od svih simbola koje smo naveli su simboli O i Θ.

Takođe imajte na umu da, iako Ω nam daje donju granicu za ponašanje naše funkcije (tj. poboljšali smo naš program tako da obavlja manje instrukcija) i dalje gledamo na analizu "najgoreg slučaja". Iz razloga što u naš program ubacujemo najgori mogući unos za dato n i analiziramo njegovo ponašanje pod pretpostavkom. Sledeća tabela prikazuje simbole koje smo uveli i njihovu prepisku sa matematičkim simbolima poređenja koje koristimo za brojeve. Razlog zašto ne koristimo uobičajene simbole ovde, već koristimo grčka slova, jeste da istaknemo da poredimo asimptotsko ponašanje, a ne samo prosto poređenje.

Operator asimptotskog poređenja	Operator brojevnog poređenja
Algoritam je o( nečeg )	Broj je < od nešto
Algoritam je O( nečeg )	Broj je ≤  nešto
Algoritam je Θ( nečeg )	Broj je  = nešto
Algoritam je Ω( nečeg )	Broj je  ≥ nešto
Algoritam je ω( nečeg )	Broj je  > od nešto

Pravilo: Dok su svi simboli O, o, Ω, ω i Θ korisni, O se najviše koristi, jer je lakši za odlučivanje od Θ i više praktičniji nego Ω.

Logaritmi

Slika 4: Poređenje funkcija n, ${\textstyle {\sqrt {n}}}$ , i log( n ). Funkcija n je linearna funkcija, nacrtana zelenom na vrhu, raste mnogo brže nego funkcija kvadratnog korena, nacrtana crvenom u sredini, za koju se ispostavlja da raste mnogo brže nego log( n ) funkcija nacrtana plavom na dnu slike. čak i za malo n kao što je n = 100, razlike su prilično primetne.

Ako znate šta logaritmi su, slobodno preskočite ovaj deo. Kako mnogo ljudi nije upoznato sa logaritmima, ili ih nisu samo koristili mnogo nedavno i zaboravili ih, ovaj deo ovde je uvod za njih.

Logaritmi su važnijer se javljaju često prilikom analiziranja složenosti. Logaritam je operacija primenjena na broj i čini ga dosta malim - slično kao kvadratni korena nekog broja. Dakle, ako postoji jedna stvar koju želite da zapamtite o logaritama je da oni uzimaju broj i čine ga mnogo manjim od originalnog (vidi sliku 4). Sada, na isti način na koji je kvadratni koren suprotna operacija od kvadriranja nečeg, logaritmi su suprotna operacija od eksponenta. Primer: pogledajte jednačinu:

2^x = 1024

Sada želimo da rešimo jednačinu za x. Pitamo se: Na koji broj treba da pogidnemo 2 da bi dobili 1024? Taj broj je 10. Stvarno, imamo 2¹⁰ = 1024, što je lako potvrditi. Logaritmi nam pomažu da zabeležimo ovaj problem upotrebom nove notacije. U ovom slučaju, 10 je logaritam od 1024 to pišemo kao log( 1024 ), a to čitamo "logaritam 1024". Zbog upotrebe 2 kao baze, ovaj logaritam se zove logaritam sa osnovom 2. Postoje logaritmi sa drugim bazama, ali u ovom članku ćemo koristiti samo bazu 2. U računarstvu, baza 2 logaritma je češća nego ostale osnove algoritma. Razlog je zato što često imamo samo dva osnovna entiteta: 0 i 1. Takođe želimo da veliki problem podelimo na pola. Tako da za ovaj članak sve što je potrebno da znate jeste samo logaritam sa osnovom (bazom) 2.
Vežba 7

Reši jednačine ispod. Označite logaritam koji tražite u svakom navedenom slučaju. Koristite osnovu 2.

1. 2^x = 64
2. (2²)^x = 64
3. 4^x = 4
4. 2^x = 1
5. 2^x + 2^x = 32
6. (2^x) * (2^x) = 64

Rešenje

Ne postoji ništa više od primene ideae definisanih gore.

1. Metodom pokušaja i grešaka možemo naći da je x = 6 i log( 64 ) = 6.
2. Ovde smo primetili da (2²)^x po osobinama eksponenata, može biti zapisano kao 2^2x. Tako imamo da je 2x = 6 jer je log(64) = 6 iz prethodnog rezultat i zato je h = 3.
3. Koristeći svoje znanje iz prethodne jednačine, možemo da napišemo 4 kao 2² i tako naš jednačina postaje (2²)^x = 4 koja je ista kao i 2^2x = 4. Onda primetimo da je log( 4 ) = 2 jer je 2² = 4 i stoga imamo da je 2^x = 2. Dakle, x = 1. Ovo je lako primetiti iz originalne jednačine, koristeći eksponent 1 daje osnovu kao rezultat.
4. Podsetimo se da eksponent 0 daje rezultat 1. Dakle, imamo log( 1 ) = 0 kao 2⁰ = 1, pa je x = 0.
5. Ovde imamo zbir pa ne možemo uzeti direktno logaritam. Međutim, primetimo da je 2^x + 2^x je isto kao 2 * (2^x). Tako smo pomnožili za dva, što je isto kao 2^{x + 1} i sada sve što moramo da uradimo je da rešimo jednačinu 2^{x + 1} = 32. Nalazimo da je log(32) = 5, odnosno x + 1 = 5, a samim tim da je x = 4.
6. Kako množimo zajedno dva puta 2 na neki stepen, možemo da ih pridružimo, tj.  (2^x) * (2^x) je isti što i 2^2x. I onda sve što treba je da rešimo jednačinu 2^2x = 64 koja je već rešena gore za x = 3.

Pravilo: Za poređenje algoritma realizovanih u C++, jednom kada analizirate složenost, možete dobiti grubu procenu koliko brzo će vaš program raditi očekujući da obavlja oko 1.000.000 operacija u sekundi, gde su operacije koje brojite date ponašanjem asimptotske funkcije opisujući vaš algoritam. Na primer, Θ ( n ) algoritam traje oko jedne sekunde da obradi ulaz za n = 1.000.000.

Rekurzivna složenost

Slika 5: Rekurzija sa funkcijom faktorijela.

Pogledajmo sada rekurzivnu funkciju. Rekurzivna funkcija je funkcija koja poziva samu sebe. Možemo li analizirati složenost? Naredna funkcija, napisana u Pajtonu, računa faktorijel broja.  Faktorijel pozitivnog celog broje se nalazi tako što se taj broj množi sa brojem za 1 manjim od njega, i to se ponavlja sve dok ne dođe do 1. Na primer, faktorijel od 5 je 5 * 4 * 3 * 2 * 1. To zapisujemo "5!", a čitamo kao"5 faktorijel".

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

Analizirajmo složenost ove funkcije. Ova funkcija nema petlje, ali njena kompleksnost nije ni konstantna. Ono što treba da uradimo da bismo saznali njenu složenost je da se vratimo na brojanje instrukcija. Jasno, ako ubacimo neko n u ovu funkciju, ona će se izvršiti n puta. Ako niste sigurni za to, prođite "ručno" sa n = 5 da potvrdite da zapravo radi. Na primer, za n = 5, ona će izvršiti 5 puta, jer će zadržati smanjenje n za 1 u svakom pozivu. Možemo dakle da vidimo da je ova funkcija onda Θ ( n ).

Ako niste sigurni o to, zapamtite da uvek možete da pronađete tačnu složenost brojanjem instrukcija. Ako želite, pokušajte da izbrojite stvarne instrukcija koje obavlja ova funkcija da dobijete funkciju f( n ) i vidite da je to zaista linearna ( prisetimo se da linearno znači Θ ( n )).

Slika 5 za dijagram će vam pomoći da razumete rekurziju kada je pozvano factorial(5). Ovo bi trebalo objasniti zašto je ova funkcija linearne složenosti.

Analizirajmo složenost ove funkcije. Ova funkcija nema petlje, ali njena kompleksnost nije ni konstantna. Ono što treba da uradimo da bismo saznali njenu složenost je da se vratimo na brojanje instrukcija. Jasno, ako ubacimo neko n u ovu funkciju, ona će se izvršiti n puta. Ako niste sigurni za to, prođite "ručno" sa n = 5 da potvrdite da zapravo radi. Na primer, za n = 5, ona će izvršiti 5 puta, jer će zadržati smanjenje n za 1 u svakom pozivu. Možemo dakle da vidimo da je ova funkcija onda Θ ( n ). Ako niste sigurni o to, zapamtite da uvek možete da pronađete tačnu složenost brojanjem instrukcija. Ako želite, pokušajte da izbrojite stvarne instrukcija koje obavlja ova funkcija da dobijete funkciju f( n ) i vidite da je to zaista linearna ( prisetimo se da linearno znači Θ ( n )). Slika 5 za dijagram će vam pomoći da razumete rekurziju kada je pozvano factorial(5). Ovo bi trebalo objasniti zašto je ova funkcija linearne složenosti.

Logaritamska složenost

Slika 6: Rekurzija pozvana binarnom pretragom. Argument A u svakom pozivu je označen crnom. Rekurzija se nastavlja sve dok ne u nizu ne ostane jedan element.

Jedan poznati problem u računarstvu jeste pronalaženje vrednosti u nizu. Mi smo ranije rešili ovaj problem za opšti slučaj. Ovaj problem postaje zanimljiv ako imamo niz koji je sortiran i želimo da pronađemo datu vrednost unutar njega. Jedan način da to uradimo zove se binarna pretraga. Gledamo elemente u sredini našeg niza: Ako ga nađemo tamo, završili smo. U suprotnom, ako je vrednost koju nađemo veća od vrednosti koju tražimo, znamo da će onda naš element biti na levom delu niza. U suprotnom, znamo da će biti na desnom delu niza. Možemo deliti te manje nizove na pola dok nam ne ostane jedan element za proveru. Taj metod upotrebom pseudokoda:

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

Ovaj pseudokod je pojednostavljenje stvarne realizacije. U praksi, ovaj metod je lakše opisati nego realizovati, jer  programer mora da brine o nekim pitanjima implementacije. Postoje jedinične greške i deljenje sa 2 ne daje uvek celobrojnu vrednost i zato je neophodno da se zaokruži vrednosti. Ali možemo pretpostaviti za naše potrebe da će uvek uspeti, i pretpostaviti da naša realizacija u stvari brine o jediničnoj greški, kao što samo želimo da analiziramo složenost ove metode. Ako nikada niste sprovodili binarnu pretragu pre, možda ćete želeti da to uradite u vašem omiljenom programskom jeziku, jer je zaista poučan poduhvat.

Slika 6 će vam pomoći da razumete kako binarna pretraga funkcioniše.

Ako niste sigurni da ova metoda stvarno radi, odvojite malo vremena i probajte je ručno na jednostavnom primeru i uverite se da zapravo radi.

Sada ćemo pokušati da analiziramo ovaj algoritam. Opet, imamo rekurzivni algoritam u ovom slučaju. Pretpostavimo, zbog jednostavnosti, da se niz uvek polovi tačno na pola, ignorišući sada  + 1 i - 1 deo u rekurzivnom pozivu. Do sada bi trebalo da budete uvereni da mala promena, kao što je ignorisanje + 1 i - 1 neće uticati na naše rezultate složenosti. Pretpostavimo da naš niz ima veličinu koja je tačno eksponent od 2, zbog jednostavnosti. Opet ova pretpostavka ne menja konačni rezultat naše složenosti do koje ćemo doći. Najgori slučaj za ovaj problem će se desiti kada se vrednost koju tražimo ne pojavljuje uopšte u našem nizu. U tom slučaju, krećemo sa nizom veličine n u prvi poziv rekurzije, onda je niz veličine n / 2 u sledećem pozivu. Onda ćemo dobiti niz veličine n / 4 u narednom rekurzivnom pozivu, a zatim niz veličine n / 8 i tako dalje. U principu, naš niz je podeljen na pola u svakom pozivu, dok ne dođemo do 1. Dakle, hajde da napišemo broj elemenata u našem nizu za svaki poziv:

1. 0. iteracija: n
2. 1. iteracija: n / 2
3. 2. iteracija: n / 4
4. 3. iteracija: n / 8
5. ...
6. i. iteracija: n / 2ⁱ
7. ...
8. poslednja iteracija: 1

Primetimo da u  i-toj iteraciji, naš niz ima n / 2ⁱ elemenata. To je zato što pri svakoj iteraciji skraćujemo niz za pola, odnosno delimo broj elemenata za dva. Ovo množi imenitelj sa 2. Ako to uradimo i  puta, dobijamo n / 2ⁱ. Ovaj postupak se nastavlja i sa svim većim i , te dobijamo manji broj elemenata dok ne stignemo do poslednje iteracije u kojoj imamo samo 1 element. Ako želimo da nađemo i da saznamo u kojoj iteraciji će ostati, moramo da rešimo sledeće jednačine:

1 = n / 2ⁱ

Ovo će biti samo tačno ako smo stigli do poslednjeg poziva binarySearch() funkcije, ne u opštem slučaju. Pa rešavanje za i će nam pomoći u kojoj iteraciji će se rekurzija završiti. Množenjem obe strane sa 2ⁱ dobijamo:

2ⁱ = n

Ove jednačine bi sada trebalo da vam budu poznate ako iz dela o logaritmima iznad. Rešavanjem za i imamo:

i = log( n )

Ovo nam govori da je broj iteracija potreban da se uradi binarna pretraga jednak log( n ) gde je n broj elemenata u početnom nizu.

Na primer, uzmimo da je n = 32, niz od 32 elementa. Koliko puta ćemo ga podeliti na pola da dobijemo samo 1 element? Dobijamo: 32 → 16 → 8 → 4 → 2 → 1. Podelili smo 5 puta, što i jeste logaritam od 32. Dakle, imamo da je složenost binarne pretrage Θ( log( n ) ).

Poslednji rezultat nam dozvoljava da poredimo binarnu sa linearnog pretragom, našom prošlom metodom. Jasno je da kako je log( n ) mnogo manje od n, zaključujemo da je binarna pretraga mnogo brži metod za pretragu elementa u nizu od linearne, pa je preporučljivo da zadržite niz sortiranim ako planirate da vršite nad njim mnogo pretraživanja.

Pravilo: Unapređenje asimptotskog vremena rada jednog programa često izuzetno povećava njegove performanse, mnogo više nego bilo koja manja "tehnička" optimizacija kao što je korišćenje bržeg programskog jezika.

Optimalno sortiranje

Sada znate o analiziranju složenosti algoritama, asimptotsko ponašanje funkcija i veliko O notaciju. Takođe znate kako da intuitivno razumete koja je složenost algoritma O( 1 ), O( log( n ) ), O( n ), O( n² ) i tako dalje. Znate simbole o, O, ω, Ω i Θ i šta analiza najgoreg slučaja znači.

Ovaj zadnji deo je izborni. On malo više uvodi, tako da možete slobodno ga preskočite, ako osećate da je ovo bilo dovoljno. On zahteva da se fokusirate i provedete nekoliko trenutaka radeći vežbe. Međutim, on će vam pružiti veoma koristan metod u analizi složenosti algoritma koji može biti vrlo moćan, tako da svakako vredi razumevanja.

Gledali smo implementaciju za sortiranje iznad nazivanu sortiranje izborom. Pomenuli smo da sortiranje izborom nije optimalno. Optimalan algoritam je algoritam koji rešava problem na najbolji mogući način, što znači da ne postoji bolji algoritam za to. To znači da svi ostali algoritmi za rešavanje problema imaju lošiju ili jednaku složenost od tog optimalnog algoritma. Može biti mnogo optimalnih algoritama za problem i da svi dele istu složenost. Problem sortiranja može biti optimalno rešen na razne načine. Možemo koristiti istu ideju kao i sa binarnom pretragom za brzo sortiranje. Ovaj metod sortiranja se zove sortiranje spajanjem.

Da bismo izvršili sortiranje spajanjem, prvo ćemo morati da izgradimo pomoćnu funkciju koja će koristiti za aktuelno sortiranje. Napravićemo funkciju spajanja koja uzima dva niza gde su oba sortirana i spaja ih zajedno u veći sortirani niz. Ovo je lako uraditi:

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 funkcija uzima element,  "glavu", i niz, "rep", i vraća novi niz koji sadrži "glavu" element kao prvu stvar u novom nizu i dati "rep" element kao ostale elemente u nizu. Na primer, concat( 3, [ 4, 5, 6 ] ) vraća [ 3, 4, 5, 6 ]. Koristimo A_n i B_n da označimo veličine niza A i B, respektivno.

Vežba 8

Proverite da li je funkcija iznad zapravo obavlja spajanje. Zapišite je u vašem omiljenom programskom jeziku na iterativan način (koristići petlje) umesto rekurzije.

Analizom ovog algoritam otkrivamo da ima pokretno vreme Θ( n ), gde je n dužina dobijenog niza (n = A_n + B_n).

Vežba 9

Proverite da li je pokretno vreme spajanja jednako Θ ( n ).

Koristeći ovu funkciju možemo izgraditi bolji algoritam za sortiranje. Ideja je sledeća: Delimo niz na dva dela. Sortiramo svaki od dva dela rekurzivno, onda spajamo dva sortirana niza u jedan veliki niz. U pseudokodu:

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 ) )

Ovu funkciju je teže razumeti nego one koje smo prošli ranije, tako da vam sledeća vežba može oduzeti nekoliko minuta.

Vežba 10

Proverite ispravnost sortiranja spajanjem. To jest, proverite da li je sortiranje spajanjem, kako je definisano gore, stvarno ispravno sortira dati niz. Ako imate problema sa razumevanjem kako to radi, probajte sa malim primerom niza i pokrenite ga "ručno". Kada pokrenete ovu funkciju ručno, uverite se da leva polovina i desna polovina budu ono što dobijete kada podelite niz približno u sredini; ne mora tačno biti u sredini ako niz ima neparan broj elemenata (to je čemu floor iznad služi).

Kao poslednji primer, analizirajmo složenost sortiranja spajanjem. U svakom koraku sortiranja spajanjem, delimo niz u dva dela jednake veličine, slično binarnoj pretrazi. Međutim, u ovom slučaju, mi održavamo obe polovine prilikom izvršenja. Zatim primenjujemo algoritam rekurzivno na svaku polovinu. Nakon rekurzivnog vraćanja, primenjujemo operaciju spajanja na rezultat koji je Θ( n ) vremena .

Dakle, podelili smo originalni niz u dva niza veličine n / 2 svaki. Onda smo spojili te nizove, operacija koja spaja n elemenata i na taj način zauzima Θ ( n ) vremena.

Pogledajte sliku 7 da shvatite ovu rekurziju.

Slika 7: Rekurzivno drvo sortiranja spajanjem.

Da vidimo šta se ovde dešava. Svaki krug predstavlja poziv funkciji mergeSort. Broj napisan u krugu ukazuje na veličinu niza koji se sortira. Plavi krug na vrhu je originalni poziv mergeSort, gde smo dobili da sortirmo niz veličine n. Strelice pokazuju rekurzivne pozive između funkcija. Početni poziv mergeSort čini dva poziva mergeSort na dva niza, svaki veličine n / 2. Ovo ukazuje na dve strelice na vrhu. Zauzvrat, svaki od ovih poziva čini dva poziva svojim funkcijama mergeSort na dva niza veličine n / 4 svaki, i tako dalje dok ne stigne do niza veličine 1. Ovaj dijagram se zove rekurzivno drvo, jer ilustruje kako se rekurzija ponaša i izgleda kao drvo (koren je na vrhu, a listovi su na dnu, tako da u stvarnosti to izgleda kao obrnuto drvo).

Obratite pažnju da u svakom redu u gornjem dijagramu, ukupan broj elemenata je n. Da vidite, pogledajte svaki red pojedinačno. Prvi red sadrži samo jedan poziv mergeSort sa nizom veličine n, tako da je ukupan broj elemenata n. Drugi red ima dva poziva mergeSort, svaki veličine n / 2. Ali n / 2 + n / 2 = n i tako ponovo, u ovom nizu ukupan broj elemenata je n. U trećem redu, imamo 4 poziva svaki od njih se primenjuje na n / 4-veličine niza, ukupan broj elemenata biće jednak n / 4 + n / 4 + n / 4 + n / 4 = 4n / 4 = n. Dakle, opet smo dobili n elemenata. Sada primetite da na svakom redu u ovom dijagramu pozivalac će morati da izvrši operaciju spajanja na elementima vraćenim pozivima. Na primer, krug označen sa crvenom bojom mora da sortira n / 2 elementa. Da bi to uradio, deli n / 2 niz veličine u dva niza n / 4 veličine, poziva mergeSort rekurzivno da sortira one (ovi pozivi su krugovi označeni zelenom bojom), a zatim ih spaja zajedno. Ova operacija spajanja zahteva da se spoji n / 2 elementa. Na svakom redu u našem stablu, ukupan broj spojenih elemenata je n. U redu koji smo istražili, naša funkcija spaja n / 2 elemenata i funkcije na njoj desno (koje su u plavoj boji) takođe ima da spoje n / 2 svojih elementa. To daje n ukupno elemenata koje treba spojiti za red koji smo gledali.

Po ovom argumentu, složenost za svaki red je Θ( n ). Znamo da broj redova u ovom dijagramu, koji se naziva i dubina rekurzije drveta, je log( n ). Razlog za to je potpuno isti kao onaj koji smo koristili prilikom analize složenost binarne pretrage. Imamo log( n ) redova i svaki od njih je Θ( n ), tako da je složenost mergeSort Θ( n * log( n ) ). Ovo je mnogo bolje nego Θ( n2 ) koje nam sortiranje izborom daje (setite se da je log( n ) mnogo manje od n, i tako je n * log( n ) znatno manje od n * n = n²). Ako ovo zvuči komplikovano za vas, ne brinite: nije lako prvi put kad vidite. Ponovo posetite ovaj odeljak i ponovo pročitajte o argumentima ovde nakon što sprovedete sortiranje spajanjem u vašem omiljenom programskom jeziku i potvrdite da radi.

Kao što ste videli u poslednjem primeru, analiza složenosti omogućava nam da uporedimo algoritme da vidimo koji je bolji. Pod ovim okolnostima, sada možemo biti prilično sigurni da će sortiranje spajanjem nadmašiti sortiranje izborom za velike nizove. Ovaj zaključak bi bilo teško izvući ako nismo imali teorijsku pozadinu analize algoritma koju smo razvili. U praksi, zaista algoritmu sortiranja je potrebno vremena Θ( n * log( n ) ). Na primer, Linuks kernel koristi algoritam za sortiranje po imenu hipsort, koji ima isto vreme rada kao sortiranje spajanjem koje je ovde istraženo, odnosno Θ( n log( n ) ) i tako da je optimalan. Primetite da nismo dokazali da su ovi algoritmi za sortiranje optimalni. To bi zahtevalo malo više uključivanja matematičkih argumenta, ali budite sigurni da oni ne mogu biti bolji sa tačke gledišta složenosti.

Nakon čitanja ovog članka, intuicija koju ste razvili za analizu složenosti algoritma bi trebalo da vam pomogne da dizajnirate brže programe i fokusirate svoje napore za optimizaciju na stvari koje su zaista važne umesto na manje stvari koje ne znače, što vam omogućava da radite produktivnije . Pored toga, matematički jezik i notacija predstavljena u ovom članku, kao što je veliko O notacija je od pomoći u komunikaciji sa drugim softverskim inženjerima kada želite da raspravljate o brzini algoritama, pa se nadam da ćete moći da to uradite sa svojim novim stečenim znanjem.

Literatura

• 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.