Analiza algoritama

U računarstvu, analiza algoritama je određivanje iznosa sredstava (kao što su vreme i skladištenje), koji su potrebni da ih izvrše. Većina algoritama je dizajnirana tako da rade sa ulazima proizvoljnih dužina. Obično se efikasnost ili potrebno vreme algoritama navodi kao funkcija koja se odnosi na dužinu ulaznog broja koraka (vremenska kompleksnost) ili prostorom za skadištenje(prostornom složenošću).

Analiza algoritama je važan deo ove velike kompeksne teorije, koja pruža teorijske procene za resurse koji su potrebni bilo kojem algoritmu, koji rešava dati račurarski problem. Ove procene daju uvid u razumne instrukcije u potrazi za efikasnijim algoritmom.

U teorijskoj analizi algoritama uobičajno je da se procenjuje njihova kompleksnost u asimpotskom smislu, odnosno da proceni funkciju složenosti za proizvoljno veliki unos. Veliko O notacija (Big O notation), Veliko-omega notacija (Big-omega notation) i Veliko-teta notacija (Big-theta notation) se koriste u ovu svrhu. Na primer, binarna pretraga podrazumeva nekoliko koraka koji su srazmerni logaritmu dužine liste koja se traži, ili u O(log(n)), jednako u logaritamskom vremenu. Obično asimpotske procene se koriste jer različite implementacije istog algoritma mogu da se razlikuju u efikasnosti. Efikasnosti bilo koje dve razumne implementacije datog algoritma su povezane stalnim multiplikativnim faktorom koji se zove skrivena konstanta.

Tačna, a ne asimpotska mera efikasnosti može ponekad biti izračunata, ali obično se zahtevaju izračunavanja uključujući određenu implementaciju algoritma, koja se zove model obračuna. Ovaj model izračunavanja može biti definisan u smislu apstraktnog računara, npr. Tjuringova mašina, i/ili da se pojedine operacije izvršavaju u jedinici vremena.

Na primer, ako se sortirana lista na koju se primenjuje binarna pretraga ima n elemenata, a ako garantujemo da svaki pronalazak elemenata iz liste može da se uradi u jedinici vremena, onda najčešće log₂ n + 1 jedinice vremena su potrebne da se vrati odgovor.

Modeli troškova[uredi | uredi izvor]

Efikasnost vremena zavisi od toga šta ćemo definisati da bude korak. Za analizu korisno je da odgovaraju stvarnom vremenu izvršavanja, treba biti oprezan ovde, na primer, neke analize računaju dva koraka kao jedan. Ova pretpostavka ne može biti opravdana u određenim situacijama. Na primer, ako brojevi koji su uključeni u obračun mogu biti proizvonjno veliki, vreme koje zahteva jedan podatak više ne može da se pretpostavlja kao konstanta.

Dva modula obračuna se obično koriste:

Uniformni model troškova, dodeljuje stalni trošak svakom mašinskom času, bez obzira na veličinu uključenih brojeva.
Logaritamski model troškova, dodeljuje trošak mašinskom času rada proporcionalnom broju bitova koji su uključeni.

Drugi model je teži za korišćenje, i koristi se samo kada je to potrebno, na primer, u analizi proizvoljne preciznosti aritmetičkih algoritama, kao i oni koji se koriste u kriptografiji.

Ključna stvar koja se često predviđa je da objavljene niže granice za probleme, često su model obračuna koji je mnogo restriktivniji u odnosu na skup operacija koje mogu da se koriste u praksi i zbog toga postoje algoritmi koji su brži od onog što se smatra mogućim.

Izvršna analiza[uredi | uredi izvor]

Izvršna analiza je teorijska klasifikacija koja procenjuje i predviđa povećanje ponestajućeg algoritma kao povećanje njgovog ulaza. Ova tema privlači veliku pažnju u računarskom svetu. Program može oduzeti sekunde, sati ili čak godine u cilju izvršavanja, u zavsnosti od toga koji algoritam se primenjuje.

Nedostaci empirijskih pokazatelja

S obzirom na to da su algoritmi nezavisni od platforme (tj. dati algoritam može biti realizovan u proizvoljnom progamskom jeziku na proizvoljnom računaru koji koristi proizvoljan operativni sistem) postoje značajni nedostaci korišćenja empirijskog pristupa koji meri komparativne performanse datog skupa algoritma.

Uzimamo na primer program koji pronalazi određenu stavku sortiranu u spisku veličine n, pretpostavimo da ovaj program realizovan na računaru A koristeći algoritam za linearnu pretragu, i računar B koji je sporiji, i koji koristi algoritam za binarnu pretragu. Merenje perfomansi na dva računara koja rade po svom programu može da izgleda otprilike ovako.

n (veličina)	Računar A vreme izvršavanja (u nano-sekundama)	Računar B vreme izvršavanja (u nano-sekundama)
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000

Na osnovu ovih pokazatelja, lako bi zaključili da računar A daleko superiorniji u efikasnosti od računara B. Međutimm ako ulazna veličina raste u dovoljnom broju, onda je ovakav zaključak pogrešan.

n (veličina)	Računar A vreme izvršavanja (u nano-sekundama)	Računar B vreme izvršavanja (u nano-sekundama)
15	7	100,000
65	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10¹²	31,536 × 10¹² ns, ili 1 godina	1,375,000 ns, ili 1.375 mili-sekunda

Računar A, koji koristi linearnu pretragu programa, pokazuje linearnu stopu rasta. Vreme izvršavanja programa je direktno proporcionalno veličini ulaza. S druge strane, računar B koji koristi binarnu pretragu programa, pokazuje logaritamsku stopu rasta. Iako je računar A navodno brži, računar B će neminovno premašiti računar A koji koristi algoritam sa manjom stopom rasta.

Pravila rasta

Neformalno, za algoritam se može reći da pokazuje stopu rasta po nalogu matematičke funkcije, ako iza određene ulazne veličine, funkcija f(n) puta pozitivna kontastanta predviđa gornju granicu ili granice za izvršenje programa tog algoritma. Drugim rečima, za ulaznu veličinu n od nekog n₀ i konstantom C , vreme izvršavanja tog algoritma nikada neće biti veći od c × f(n). Ovaj koncept se često izražava u notaciji velikog O. Veliko O notacija je pogodan način da se izrazi najgori scenario za dati algoritam, mada može da se koristi i za prosečne slučajeve.

Empirijski nalozi rasta

Pod pretpostavkom na vreme izvršenja, sledi pravilo za napajanje $\approx k n a$ , koeficijent a se može naći uzimanjem empirijskih mera vremena izvršenja $\{t1,t2\}$ za neki problem veličine $\{n1,n2\}$ , računajući $t_{2}/t_{1}=(n_{2}/n_{1})^{a}$ tako da $a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1})$ . Ako naredba rasta zaista prati pravilo napajanja, empirijska vrednost od a će ostati konstantna na različitim nivoima, ako ne, to će se promeniti, ali i dalje može da posluži za poređenje bilo koja dva algoritma. Primena je na tabeli

n (veličina)	Računar A vreme izvršavanja (u nano-sekundama)	redosled rasta (n^_)	Računar B vreme izvršavanja (u nano-sekundama)	redosled rasta (n^_)
15	7		100,000
65	32	1.04	150,000	0.28
250	125	1.01	200,000	0.21
1,000	500	1.00	250,000	0.16
...	...		...
1,000,000	500,000	1.00	500,000	0.10
4,000,000	2,000,000	1.00	550,000	0.07
16,000,000	8,000,000	1.00	600,000	0.06
...	...		...

Jasno se vidi da prvi algoritam pokazuje linearno pravilo rasta posle pravila za napajanje. Empirijske vrednosti za drugi algoritam se brzo smanjuju, sugerišući da postoji još jedno pravilo rasta, i u svakom slučaju, emprijski posmatrano, ima manji rast od onog prvog.

Procena izvršne kompleksnosti[uredi | uredi izvor]

Izvršna komplsnost za najgori mogući scenario datog algoritma može ponekad biti ocenjena ispitivanjem strukture algoritma i donošenjem nekih pojednostavljenih pretpostavki. Razmotrimo sledeći pseudokod:

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

Računar će dati diskretnu količinu vremena za izvršenje svakog od uputstva koji su uključeni u sprovođenje ovog algoritma. Određeni iznos vremena da sprovede date instrukcije razlikovaće se u zavisnosti od instrukcija koje se izvršavaju i koji računar to vrši, ali je na klasičnom računaru, ovaj iznos će biti deterministički. Recimo da radnje koje su sprovedene u koraku 1 troše vreme T1, korak 2 troši vreme T2, i tako dalje.

U algoritmu gore, koraci 1,2 i 7 samo će se jednom izvršiti. Za najgoru moguću evaluaciju, treba pretpostaviti da će biti korak 3. Tako je ukupan iznos vremena za pokretanje korake 1-3 i 7 jeste:

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

Petlje u koracima od 4, 5 i 6 je teže proceniti. Spoljna petlja u 4. koraku će se izvršiti (n + 1) puta, koji će trošiti T4(n + 1) vreme. Unutrašnja petlja ide od 1 do n. Na prvom prolazu kroz spoljašnju petlju, j ide od 1 do 1. Unutrašnja petlja ima jedan prolaz, pa radi unutrašnje telo petlje (korak 6) troši vreme T6, a unutrašnja petlja (korak 5) troši vreme 2T5. Tokom narednog prolaza kroz spoljašnju petlju, j ide od 1 do 2, unutrašnja petlja ima dva mesta, tako da radi unutrašnje telo petlje (korak 6) troši vreme 2T6, a unutrašnja petlja (korak 5) troši vreme 3T5. Sve u svemu, ukupno vreme potrebno za pokretanje unutrašnjeg tela petlje se može izraziti kao aritmetička progresija:

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

koje se može uzeti, kao

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

Ukupno vreme potrebno za pokretanje unutrašnje tela petlje može biti slično:

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

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

koje se može uzeti, kao

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

Dakle ukupno vreme izvršavanja ovog algoritma je:

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

koje se svodi na

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

Kao pravilo palca, može se prepostaviti da najviši izraz u svakoj funkciji ističe svoju stopu rasta i time definiše svoje breme izvršavanja. U ovom primeru n²je najviši rede, pa se može zaključiti da je f(n) = O(n²). Formalno se to može dokazati na sledeći način

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

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

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

Neka je k konstanta veća ili jednaka od[T₁..T₇]

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

stoga $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}$ for $c=12k,n_{0}=1$ Elegantniji pristup analizi ovag algoritam bio bi da se izjasne da [T₁..T₇] su svi jednaki jedinici vremena veća ili jednaka od[T1 .. T7]. Ovo bi značilo da se vreme izvršavanja algoritma razlaže na sledeći način:</ref>

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

Stopa rasta analize drugih resursa

Metodologije izvršne analize mogu se koristiti za predviđanje i druge stope rasta, kao što su konzumiranje memorijskog prostora. Kao primer, razmotrite sledeći pseudokod koji upravlja i ponovo dodeljuje zauzeće memorije programom na osnovu veličine fajla kojim ovaj program upravlja:

while (file still open)

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

U ovom slučaju, kao što se veličina datoteke n puta povećava, memorija se konzumira eksponencijalnom stopom rasta, što bi O(2ⁿ). Ovo je izuzetno brza i verovatno neizvodljiva stopa rasta za potrošnju memorijskih resursa.

Značaj[uredi | uredi izvor]

Analiza algoriama je važna u praksi, jer slučajno ili nenamerno korišćenje neefikasnih algoritama može značajno uticati na performanse sistema. U vremenski osetljive primene, algoritmu je potrebno previše vremena za pokretanje, što može da pruži zastarele ili beskorisne rezultate. Neefikasan algoritam može zahtevati neracionalnu veliku količinu računarske moći ili skladištenja kako bi se upravljalo, čineći ga praktično neupotrebljivim.