Za usporedbu algoritama uobičajeno je koristiti generaliziranu karakteristiku koja se naziva učinkovitost. Kažu da algoritam L, učinkovitije algoritam A 2, ako je algoritam L, izvodi se u manje vremena i (ili) zahtijeva manje računalni resursi (RAM memorija, prostor na disku, mrežni promet itd.).
Učinkovit algoritam mora zadovoljiti zahtjeve prihvatljivog vremena izvršenja i razumne potrošnje resursa, kao što je već spomenuto u paragrafu 1.1. Kombinacija ovih karakteristika čini koncept složenosti algoritma. Kako se vrijeme izvršenja algoritma i/ili uključeni resursi povećavaju, složenost se povećava. Stoga su koncepti učinkovitosti i složenosti obrnuti jedan drugome.
Karakteristika algoritma koja odražava vrijeme utrošeno na njegovu implementaciju naziva se vremenska složenost. Poziva se karakteristika algoritma koja odražava troškove računalnih resursa njegove implementacije kapacitivna složenost.
U kvantitativnoj i kvalitativnoj procjeni algoritma za određivanje složenosti koriste se dva pristupa - praktični i teorijski.
Praktičan pristup povezan sa stvarno izvedenim algoritmima na određenim fizičke uređaje. Karakteriziraju ga parametri koji se mogu mjeriti i bilježiti. Vremenska složenost u ovom pristupu može se izraziti u vremenskim jedinicama (na primjer, milisekundama) ili brojem procesorskih ciklusa utrošenih na izvršavanje algoritma. Kapacitivna složenost može se izraziti u bitovima (ili drugim jedinicama informacija), minimalnim hardverskim zahtjevima potrebnim za izvršavanje algoritma itd.
Praktična procjena nije apsolutni pokazatelj učinkovitosti algoritma. Kvantitativne vrijednosti dobivene ovim pristupom ovise o mnogim čimbenicima, kao što su:
- tehnički podaci komponente koje čine računalni sustav. Dakle, viši taktna frekvencija rad procesora, što se više elementarnih operacija može izvršiti u jedinici vremena;
- karakteristike softverskog okruženja (broj pokrenuti procesi, algoritam planera zadataka, značajke rada operacijski sustav itd.);
- odabrani programski jezik za implementaciju algoritma. Program napisan na jeziku visoke razine vjerojatno će raditi sporije i zahtijevat će više resursa nego program napisan na jezicima niske razine koji ima izravan pristup hardverskim resursima;
- iskustvo programera koji je implementirao algoritam. Najvjerojatnije će programer početnik napisati manje učinkovit program od iskusnog programera.
Stoga, algoritam koji se izvodi na istom računalnom sustavu za iste ulazne podatke može imati različite kvantitativne procjene u različitim vremenskim točkama. Stoga je teorijski pristup definiranju složenosti važniji.
Teorijska složenost karakterizira algoritam bez pozivanja na specifičnu opremu, softver i sredstva provedbe. U ovom slučaju vremenska složenost se izražava u broju operacija, ciklusa rada Turingovog stroja itd. Kapacitivna složenost određena je količinom podataka (ulazni, posredni, izlazni), brojem uključenih ćelija na vrpci Thjoring stroja itd.
U teoretskom pristupu ocjenjivanju učinkovitosti, pretpostavlja se da se algoritam izvršava na nekom idealizirano računalo, za koje je vrijeme izvršenja svake vrste operacije poznato i konstantno. Također se smatra da su resursi takvog računala beskonačni, pa se kapacitivna složenost obično ne određuje teorijskim pristupom. Broj instrukcija (operacija) izvedenih na idealiziranom računalu odabran je kao vremenska karakteristika složenosti.
Kvantitativne procjene dobivene korištenjem teorijskog pristupa također mogu ovisiti o nizu sljedećih čimbenika:
- volumen ulaznih podataka. Što je veći, to će više vremena biti potrebno za izvršenje algoritma;
- odabrani način rješavanja problema. Na primjer, za veliku količinu ulaznih podataka, algoritam brzog sortiranja učinkovitiji je od algoritma sortiranja u obliku mjehurića, iako daje isti rezultat.
Vrijeme izvršenja algoritma obično ovisi o količini ulaznih podataka (input size), što se podrazumijeva kao dimenzija problema koji se rješava. Dakle, pri sortiranju skupa vrijednosti, volumen podataka je broj elemenata tog skupa. Kod obrade nizova, veličina ulaznog podatka je duljina niza.
Neka P - količina ulaznih podataka za neki algoritam. Označimo sa T(p) broj instrukcija koje se izvršavaju na idealiziranom računalu pri izvođenju algoritma, a određuje se za “najgori slučaj” kada je volumen operacija maksimalan.
Koncept "najgoreg slučaja" može se ilustrirati primjerom. Razmotrimo algoritam za provjeru prisutnosti numeričkog elementa u određenom skupu (nizu) brojeva. Ako je ovaj skup poredan uzlaznim redoslijedom, onda, općenito govoreći, nema smisla provjeravati elemente koji se nalaze iza prvog elementa koji je veći od traženog. U ovom slučaju T(p) itd. Međutim, u najgorem slučaju (za proizvoljan nesortirani skup), morat ćete pregledati sve elemente skupa. Očito ovdje T(p) = p.
Općenito govoreći, T(p) je neka funkcija količine ulaznih podataka P. U puno slučajeva T(p) izražen kao polinom, potencija ili logaritamska funkcija od P.
Ponašanje količine T(p) ovisno o povećanju P nazvao asimptotska složenost algoritam. To kažu T(str) Ima redoslijed složenosti 0(J(n))(čita "OKO veliki od/iz P") za neki algoritam, ako postoje konstante S i količina podataka sch takav da GORE > n 0 i postoji nejednakost T(str) s/(p).
Ova činjenica je napisana kao T(n) = 0(J(n)) a znači da za funkciju T(p) postoji takva funkcija f(n) i konstantu c, za koju, počevši od nekih n 0, značenje T(p) ne prelazi cf(n).
Funkcija f(n) predstavlja gornju granicu vrijednosti funkcije T(n). Neka npr. T(n) = 2str A + n 2. Odabir vrijednosti n 0= 0 i c = 5, za bilo koga n > n 0 imamo T(n) = 2str A + n 2 T(n) je reda i 4.
Funkcija T(str) povezan je s određenim algoritmom, pa se često kaže da je redoslijed složenosti 0(/(n)) ima točno algoritam.
To kažu T(p) Ima donja granica Q(g(n))(čita se "omega velika od g iz /g"), ako postoji konstanta c i količina podataka n 0 takav da /P i postoji nejednakost T(n) > cg(n).
Ova činjenica je napisana kao T(n) = Q(g(n)). Neka npr. T(n) = 2. 4 + n 2. Odabir vrijednosti c = 1, za bilo koga P imamo T(p)= 2. 4 + p 2 > sp A > stoga, T(str) ima donju granicu i 4 .
Lako je vidjeti da redoslijed i donja granica nisu jedinstveni za neku funkciju T(n). U gornjim primjerima, moglo se odabrati i 5 , i 6 ,... kao /(i) i as g(n) - i 3, i 2,.... Obično se funkcija s minimalnim stupnjem bira kao /(i), a kao g(n)- s maksimumom.
Redoslijed složenosti 0(/(i)) i donja granica Q(g(rc)) predstavljaju klase funkcija. Intuitivno, Q(g"(n)) se može shvatiti kao klasa funkcija koje rastu barem jednako brzo kao T(n). Isto tako, intuitivno 0(f(n)) može se shvatiti kao klasa funkcija koje rastu ne brže od T(n). S S praktičnog gledišta, pri procjeni složenosti algoritma najvažnija stvar je klasa funkcija 0(f(n)). Određivanje vrste funkcije /(i) je glavni zadatak proračuna teorijska složenost algoritma.
Za bilo koji algoritam, pri određivanju stupnja rasta, možete koristiti sljedeća svojstva 0(/(i)):
1) 0(kf(ji))= 0(/(i)), gdje je k= konst. Dakle, konstantni množitelj u funkciji ne utječe na stopu rasta. Na primjer,
2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Dakle, poredak umnoška dviju funkcija jednak je umnošku njihove složenosti. Na primjer,
Ponekad se ovo svojstvo piše kao
3) 0(/(p) + g(n)) jednaki dominantan(funkcije s maksimalnim stupnjem) funkcije /(i) i g(n). Na primjer,
U teoriji složenosti algoritama razlikuju se sljedeće klase funkcija složenosti:
- 1) konstantna složenost 0(1). Vrijeme rada algoritma i korišteni resursi ne ovise o količini ulaznih podataka. Tipično, algoritmi koji ne sadrže petlje i rekurzivne pozive imaju ovu složenost;
- 2) linearna složenost 0(n). Obično se takva složenost nalazi u zadacima u kojima se svaki element ulaznih podataka mora obraditi određeni broj puta, što ni na koji način nije povezano s brojem obrada ostalih elemenata;
- 3) logaritamska složenost 0(log 2 w), 0(nog 2 n). Ponekad se koriste i druge logaritamske baze;
- 4) polinomska složenost 0(i 2), 0(i 3), 0(i 4),...;
- 5) eksponencijalna složenost 2 p, 3",....
Kako se veličina unosa povećava, složenost svake sljedeće vrste funkcije raste brže od prethodne (osim za 0(log 2 /?)). Za dovoljno veliku količinu ulaznih podataka poželjno je koristiti algoritme manje složenosti.
Pri kvantitativnom izračunavanju složenosti inicijalno se odabire operacija ili skupina operacija koja je značajna za ovaj algoritam (čini njegovu osnovu). Obično su to operacije usporedbe i aritmetičke operacije. Operacije usporedbe uključuju provjeru vrijednosti dviju veličina (manje od, veće od, jednako, manje od ili jednako, veće od ili jednako, nije jednako). Smatraju se ekvivalentnima u vremenu izvršenja. Aritmetičke operacije se pak dijele na aditiv I multiplikativni. Prvom (često se naziva jednostavno dodatak) uključuju dodavanje, oduzimanje, dekrementiranje ili dekrementiranje protuvrijednosti. Drugom (nazvanom jednostavno množenje) uključuju množenje, dijeljenje, modulo.
Operacije zbrajanja su brže od operacija množenja, pa se preferiraju algoritmi s manje množenja, čak i ako se broj zbrajanja povećava proporcionalno broju smanjenih množenja.
Operacije cjelobrojnog množenja ili dijeljenja potencijama broja 2 klasificiraju se kao aditivne operacije, jer se pri radu s memorijskim ćelijama svode na pomak, što je ekvivalentno operaciji zbrajanja.
Nakon odabira značajnih operacija, one se dijele u dvije kategorije:
- 1) operacije koje izravno utječu na složenost algoritma;
- 2) operacije koje čine "opterećenje" prilikom izvršavanja algoritma (na primjer, dodjela memorije za pohranu međupodataka).
Izravno brojanje ili procjena broja izvedenih operacija omogućuje procjenu T(n).
Analiza se može koristiti za procjenu reda složenosti programski kod, implementirajući algoritam. pri čemu:
- algoritmi bez petlji i rekurzivnih poziva imaju složenost reda 0(1). Dakle, operacije dodjele, unosa i izlaza podataka, kondicionali imaju stalnu složenost;
- ako dva dijela programskog koda imaju poteškoća 0(J((ri)) I 0(J 2 (n)), tada je sekvencijalno izvođenje složeno
- ako se tijelo petlje izvodi jednom za svaki element ulaznog podatka, tada je složenost izvođenja petlje reda veličine 0(n)0( 1) = 0(n);
- redoslijed složenosti izvođenja ugniježđenih petlji izračunava se pomoću pravila umnoška 0(J x (n)f 2 (n)) = 0(/,(/?))- 0(J 2 (ri)). Ako svaki od njih ima složenost reda 0(n), izvođenje ugniježđenih petlji ima složenost reda veličine 0(n 2).
Primjer 1.3
Odredite redoslijed složenosti programskog algoritma u jeziku
Pascal prikazan u ispisu 1.2. Linije programa označene su brojevima kao komentari (vidi paragraf 2.6).
Listing 1.2
(01) za i:=l do n učiniti
(02) početi
(03) write("Unesite element niza
s indeksom ",i,": ");
(04) Readln(Moj niz[i]);
(05) kraj;
(06) za i:=l do n učiniti
(07) za j:=1 do n učiniti
(08) početi
(09) write("Unesite element niza
s indeksima ", i, ",", j, " : ");
(10) Readln(MyDArray);
(11) kraj;
Riješenje
Linije 02, 05, 08, 11 ne sadrže izvršne naredbe, pa se ne uzimaju u obzir pri određivanju naloga.
Linije 03 i 04 imaju redoslijed 0(1). Njihovo sekvencijalno izvođenje ima redoslijed 0(1) + 0(1) = 0(1). Slično, izvođenje redaka 09 i 10 uzastopno ima složenost 0(1).
Petlja u recima 01-05 ima složenost reda Na), ugniježđene petlje u redovima 06-11 - poredak 0(n 2). Konačna složenost algoritma je reda veličine
Procjena složenosti algoritma, kako vremena tako i resursa, omogućuje nam da odredimo maksimalno i prosječno vrijeme izvršenja algoritma. Ovo je izuzetno važno kada se obrađuju velike količine informacija, posebno u zadacima sortiranja i pretraživanja o kojima se govori u nastavku.
Često je moguće smisliti više od jednog algoritma za rješavanje istog problema. S tim u vezi, postavlja se pitanje: koji je od algoritama “bolji”?
U većini slučajeva “bolji” je naizgled algoritam koji koristeći iste ulazne podatke dolazi do rješenja problema, trošeći manje računalnih resursa (memorije i vremena). Ovo, naravno, nije rigorozno obrazloženje. Za rigorozniju raspravu, uvodimo nekoliko pojmova.
Računalni proces algoritma je niz koraka koji se poduzimaju prilikom izvršavanja algoritma za neke ulazne podatke.
Važno je razumjeti razliku između samog algoritma i računskog procesa koji taj algoritam generira. Prvi je samo opis drugi.
Vremenska složenost algoritma je vrijeme \(T\) potrebno da se dovrši računski proces algoritma za neke ulazne podatke.
Jasno je da vrijeme izvršenja ovisi o konkretnog izvođača. Recimo, elektronički kalkulator i superračunalo vjerojatno će pokretati isti algoritam za različita vremena.
Međutim, vrijeme \(T\) može se izraziti kroz broj elementarnih radnji \(k\) i prosječno vrijeme za dovršenje elementarne radnje \(t\):
Štoviše, \(k\) je svojstvo sam algoritam, a \(t\) je svojstvo izvođača.
Zbog činjenice da se \(t\) može smatrati konstantom za danog izvršitelja, složenost algoritama se obično procjenjuje do konstantnog faktora. Drugim riječima, procjenjuje se složenost algoritma red rasta.
Red rasta Pozitivno određena funkcija \(g(x)\) ima red rasta \(f(x)\) (napisano \(g(x)=\mathcal(O)(f(x))\)) ako \(\postoji c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).
Ovisno o ulaznim podacima, algoritam može raditi različita vremena. Obično se procjenjuje prosjek složenost i složenost U najgorem slucaju. Postoji i ovisnost o količinama ulazni podaci \(n\) . Obično se procjenjuje redoslijed rasta od \(n\).
Tako će, na primjer, čitanje podataka i njihovo pohranjivanje u memoriju kao niza biti složeno \(\mathcal(O)(n)\) , ili linearna složenost, a množenje matrice je već kubični\(\mathcal(O)(n^3)\) .
Osim vremenske složenosti algoritma, ona se također pokazuje važnom prostorni složenost algoritma.
Prostorna složenost algoritma je broj dodatni memorija \(S\) koju algoritam zahtijeva za rad. Memorija \(D\) potrebna za pohranjivanje ulaznih podataka nije uključena u \(S\).
\(S\) u općem slučaju također ovisi o aktuatoru. Recimo, ako dva izvršna uređaja podržavaju cijele brojeve duljine 4, odnosno 8 bajtova, tada će prostorna složenost algoritma na 8-bajtnim cijelim brojevima biti dvostruko veća nego na 4-bajtnim cijelim brojevima. Stoga se prostorna složenost procjenjuje i redoslijedom rasta.
Klase složenosti algoritama
Određeno klase težine: Ovo su kategorije slične složenosti.
Razlikuju se sljedeće glavne klase težine:
DVRIJEME Turingov stroj pronalazi rješenje problema u konačnom vremenu (broju koraka). Asimptotsko ponašanje algoritma je često specificirano, pa, recimo, ako je redoslijed povećanja radnog vremena \(T(n) = \mathcal(O)(f(n))\), tada navedite \(DTIME(f (n))\) . P Turingov stroj pronalazi rješenje problema u polinomnom vremenu (broj koraka), tj. \(T(n) = \mathcal(O)(n^k)\) , gdje \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME Turingov stroj pronalazi rješenje problema u eksponencijalnom vremenu (broj koraka), tj. \(T(n) = \mathcal(O)(2^(n^k))\), gdje je \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Turingov stroj pronalazi rješenje problema koristeći konačnu količinu dodatne memorije (ćelija). Asimptotsko ponašanje algoritma je često specificirano, pa, recimo, ako je redoslijed rasta u potrošnji memorije \(S(n) = \mathcal(O)(f(n))\), tada navedite \(DSPACE(f (n))\) . L Turingov stroj pronalazi rješenje problema s logaritamskom prostornom složenošću, tj. \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE Turingov stroj pronalazi rješenje za problem s kompleksnošću prostora polinoma, to jest \(S(n) = \mathcal(O)(n^k)\) , gdje \(k\in \mathbb(N)\ ) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE Turingov stroj pronalazi rješenje problema eksponencijalne prostorne složenosti, tj. \(S(n) = \mathcal(O)(2^(n^k))\), gdje je \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .
Osim toga, postoje teorijske klase složenosti koje rade na konceptu nedeterministički Turingovi strojevi (TMT). Njihove definicije su iste kao gore, s Turingovim strojem zamijenjenim s NMT, a njihovim imenima s prefiksom N (na primjer, NP), osim za NTIME i NSPACE, gdje je D zamijenjen s N.
NMT je čisto teorijska konstrukcija, koja je po principima rada slična MT-u, s tom razlikom da za svako od stanja može postojati neki moguće akcije. Pritom NMT uvijek od mogućih akcija odabire onu koja dovodi do rješenja u minimalno mogućem broju koraka. Isto tako, NMT izvodi izračune svatko grane i odabire granu koja vodi do rješenja u minimalnom mogućem broju koraka.
Ponekad možete čuti da su kvantna računala implementacija NMT-a. Iako se to može činiti istinitim u nekim slučajevima, općenito LBW je više moćan sustav nego kvantno računalo.
Poznato je da \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq SLJEDEĆE VRIJEME \subseteq EXPSPACE\)
Osim toga, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)
Također je poznato da ako \(P = NP\) tada \(EXPTIME = NEXPTIME\) .
Pitanje jednakosti P i NP jedno je od glavnih neriješenih pitanja moderne računalne znanosti.
Primjeri algoritama
Navedimo neke primjere jednostavnih algoritama i razmotrimo njihovu složenost.
Podizanje na cijelu snagu
Ovaj algoritam je opisan u staroj Indiji prije naše ere i koristi se za izračunavanje prirodne snage \(n\) pravi broj\(x\)
- Upišite \(n\). binarni sustav mrtvi obračun
- Zamijenite u ovom unosu svaku 1 s parom slova KH, a svaku 0 slovom K
- Prekriži krajnji lijevi par KX
- Čitajući dobiveni niz s lijeva na desno, pri susretu sa slovom K rezultat kvadrirajte, a pri susretu sa slovom X rezultat pomnožite s x. Na početku rezultat je x.
U ovom algoritmu imamo broj operacija množenja jednak broju znamenki u binarnom prikazu \(n\) u najboljem slučaju i \(2(n-1)\) u najgorem slučaju. U svakom slučaju, vremenska složenost.
Za učinkovitu implementaciju algoritma praktički nije potrebna dodatna memorija, a ona ne ovisi o ulaznim podacima, pa je prostorna složenost \(S(n) = \mathcal(O)(1)\) .
Treba napomenuti da postoje učinkovitiji algoritmi. Međutim, u usporedbi s "naivnom" implementacijom koja zahtijeva \(\mathcal(O)(n)\) operacije množenja, ovaj je algoritam relativno učinkovit.
Množenje cijelih brojeva
Ovaj algoritam množenja ponekad se naziva ruskim ili seljačkim, iako je bio poznat još u starom Egiptu.
Prvi faktor se uzastopno množi s dva, a drugi se dijeli s 2. Rezultati se upisuju u dva stupca dok se u drugom ne dobije 1.
Rezultat množenja je zbroj brojeva u prvom stupcu, nasuprot kojih su neparni brojevi u drugom stupcu.
Budući da se cjelobrojno dijeljenje i množenje s 2 može implementirati pomakom, ovaj algoritam proizvodi \(2 \log_2 n\) operacije pomaka, gdje je \(n\) manji od ta dva broja. U najgorem slučaju, isto rezultira \(\log_2 n - 1\) operacijama zbrajanja. U svakom slučaju, vremenska složenost \(T(n) = \mathcal(O)(\log n)\).
Za učinkovitu implementaciju algoritma praktički nije potrebna dodatna memorija i ne ovisi o ulaznim podacima, dakle \(S(n) = \mathcal(O)(1)\)
Opet, treba napomenuti da postoje učinkovitiji algoritmi. Međutim, u usporedbi s "naivnom" implementacijom koja zahtijeva \(\mathcal(O)(n)\) operacije zbrajanja, ovaj algoritam je relativno učinkovit.
Primjer
Množenje 23 sa 43.
Uzmimo 23 kao drugi faktor.
| 43 | 23 | neparan |
| 86 | 11 | neparan |
| 172 | 5 | neparan |
| 344 | 2 | |
| 688 | 1 | neparan |
Rezultat \(43+86+172+688 = 989\)
Imamo 10 operacija pomaka i 4 operacije zbrajanja. Za referencu, \(\log_2(23) \približno 4,52\) .
Važno je da svaki programer poznaje osnove teorije algoritama, jer je to znanost koja proučava Opće karakteristike algoritmi i formalni modeli njihove reprezentacije. Još od satova informatike učili su nas izrađivati dijagrame toka, što kasnije pomaže u pisanju složenijih problema nego u školi. Također nije tajna da gotovo uvijek postoji nekoliko načina za rješavanje određenog problema: neki uključuju trošenje puno vremena, drugi resurse, a treći samo pomažu da se približno pronađe rješenje.
Uvijek treba tražiti optimum u skladu sa zadatkom, posebno kada razvijate algoritme za rješavanje klase problema.
Također je važno procijeniti kako će se algoritam ponašati s početnim vrijednostima različitih volumena i količina, koje će resurse zahtijevati i koliko će vremena trebati da se ispiše konačni rezultat.
Ovo je predmet grane teorije algoritama – teorije asimptotske analize algoritama.
U ovom članku predlažem opisati glavne kriterije ocjenjivanja i dati primjer ocjenjivanja jednostavnog algoritma. Habrahabr već ima informacije o metodama za procjenu algoritama, ali je namijenjen uglavnom studentima gimnazije. Ova se publikacija može smatrati proširenjem tog članka.
Definicije
Glavni pokazatelj složenosti algoritma je vrijeme potrebno za rješavanje problema i količina potrebne memorije.
Također, prilikom analize složenosti za klasu problema, određuje se određeni broj koji karakterizira određenu količinu podataka - veličina ulaza.
Dakle, možemo to zaključiti složenost algoritma je funkcija veličine ulaza.
Složenost algoritma može biti različita za istu veličinu ulaza, ali različite ulazne podatke.
Postoje koncepti složenosti u najgori, prosjek ili najbolji mogući scenarij. Obično se složenost procjenjuje u najgorem slučaju.
Vremenska složenost u najgorem slučaju, to je funkcija ulazne veličine, jednaka maksimalnom broju operacija izvedenih tijekom rada algoritma pri rješavanju problema zadane veličine.
Kapacitivna složenost u najgorem slučaju, funkcija ulazne veličine jednaka maksimalnom broju memorijskih ćelija kojima se pristupilo prilikom rješavanja problema zadane veličine.
Redoslijed rastuće složenosti algoritama
Redoslijed rastuće težine(ili aksiomatska složenost) opisuje približno ponašanje funkcije složenosti algoritma kada je ulazna veličina velika. Iz ovoga slijedi da pri procjeni vremenske složenosti nema potrebe razmatrati elementarne operacije, već je dovoljno uzeti u obzir korake algoritma.
Korak algoritma– skup sekvencijalno poredanih elementarnih operacija, čije vrijeme izvršenja ne ovisi o veličini ulaza, odnosno ograničeno je odozgo određenom konstantom.
Vrste asimptotskih ocjena
O – najgora procjena
Uzmite u obzir složenost f(n) > 0, funkcija istog reda g(n) > 0, veličina ulaza n > 0.
Ako f(n) = O(g(n)) a postoje konstante c > 0, n 0 > 0, To
0 < f(n) < c*g(n),
Za n > n 0.
Funkcija g(n) u ovom slučaju je asimptotski točna procjena f(n). Ako je f(n) funkcija složenosti algoritma, tada je poredak složenosti definiran kao f(n) – O(g(n)).
Ovaj izraz definira klasu funkcija koje rastu ne brže od g(n) do konstantnog faktora.
Primjeri asimptotskih funkcija
| f(n) | g(n) |
|---|---|
| 2n 2 + 7n - 3 | n 2 |
| 98n*ln(n) | n*ln(n) |
| 5n+2 | n |
| 8 | 1 |
Ω – procjena za najbolji slučaj
Međutim, definicija je slična procjeni najgoreg slučaja
f(n) = Ω(g(n)), Ako
0 < c*g(n) < f(n)
Ω(g(n)) definira klasu funkcija koje rastu ne sporije od funkcije g(n) do konstantnog faktora.
Θ – procjena za prosječni slučaj
Vrijedno je samo spomenuti da u ovom slučaju funkcija f(n) na n > n 0 posvuda je između c 1 *g(n) I c 2 *g(n), gdje je c konstantni faktor.
Na primjer, kada f(n) = n 2 + n; g(n) = n 2.
Kriteriji za ocjenu složenosti algoritama
Uniformni kriterij težine (UWC) pretpostavlja da se svaki korak algoritma izvodi u jednoj jedinici vremena, a memorijska ćelija u jednoj jedinici volumena (do konstante).
Logaritamski težinski kriterij (LWC) uzima u obzir veličinu operanda koji se obrađuje određenom operacijom i vrijednost pohranjenu u memorijskoj ćeliji.
Vremenske poteškoće za DEX određena vrijednošću l (Op), Gdje O str– vrijednost operanda.
Kapacitivna složenost u LVK određena vrijednošću l(M), Gdje M– veličina memorijske ćelije.
Primjer procjene složenosti pri izračunu faktorijela
Potrebno je analizirati složenost algoritma za izračun faktorijela. Da bismo to učinili, napišimo ovaj zadatak u C pseudokodu:
Void main() ( int rezultat = 1; int i; const n = ...; for (i = 2; i<= n; i++) result = result * n; }
Vremenska složenost s jedinstvenim kriterijem težine
Dovoljno je jednostavno utvrditi da je ulazna veličina zadanog problema n.
Broj koraka – (n - 1).
Dakle, vremenska složenost pod RVC jednaka je Na).
Vremenska složenost s logaritamskim težinskim kriterijem
U ovom trenutku trebali biste istaknuti operacije koje je potrebno ocijeniti. Prvo, to su operacije usporedbe. Drugo, operacije mijenjanja varijabli (zbrajanje, množenje). Operacije dodjele se ne uzimaju u obzir jer se pretpostavlja da su trenutne.
Dakle, u ovom zadatku postoje tri operacije:
1) ja<= n
Na i-tom koraku ispada log(n).
Od koraka (n-1), složenost ove operacije bit će (n-1)*log(n).
2) i = i + 1
Na i-tom koraku ispada log(i).
.
3) rezultat = rezultat * i
Na i-tom koraku ispada log((i-1)!).
Dakle, zbroj je 
.
Ako zbrojite sve dobivene vrijednosti i odbacite članove koji očito rastu sporije s porastom n, dobivamo konačni izraz 
.
Kapacitivna složenost s jedinstvenim težinskim kriterijem
Ovdje je sve jednostavno. Potrebno je prebrojati broj varijabli. Ako problem koristi nizove, svaka ćelija niza smatra se varijablom.
Budući da broj varijabli ne ovisi o veličini ulaza, složenost će biti jednaka O(1).
Kapacitivna složenost s logaritamskim težinskim kriterijem
U tom slučaju trebate uzeti u obzir najveću vrijednost koja se može pohraniti u memorijsku ćeliju. Ako je vrijednost nedefinirana (na primjer, kada je operand i > 10), tada se pretpostavlja da postoji neka vrsta granične vrijednosti Vmax.
U ovom problemu postoji varijabla čija vrijednost ne prelazi n(i), i varijablu čija vrijednost ne prelazi n! (proizlaziti). Dakle rezultat je O(log(n!)).
zaključke
Proučavanje složenosti algoritama prilično je fascinantan zadatak. Trenutno je analiza najjednostavnijih algoritama uključena u nastavne planove i programe tehničkih specijalnosti (točnije, općeg smjera "Informatika i računarstvo") koji se bave računarstvom i primijenjenom matematikom u području IT-a.
Na temelju složenosti razlikuju se različite klase zadataka: P, NP, NPC. Ali to više nije problem u teoriji asimptotske analize algoritama.
Poteškoća funkcije 0(1). U algoritmima konstantne složenosti većina operacija u programu izvodi se jednom ili više puta. Svaki algoritam koji uvijek zahtijeva (bez obzira na veličinu podataka) istu količinu vremena ima konstantnu složenost.
Funkcija složenosti 0(N). Vrijeme izvođenja programa obično je linearno, gdje svaki element ulaznih podataka treba obraditi samo linearni broj puta. Ova funkcija složenosti karakterizira jednostavan ciklus.
Funkcija složenosti 0(N 2), 0(N 3), 0(№) - funkcija polinomske složenosti: broj operacija raste s kvadratom N. U općem slučaju može biti O(A^), ovisno o složenosti problema. Ova funkcija složenosti karakterizira složeni ciklus.
Poteškoća funkcije O(Dnevnik 2 (A0), 0(N log2(A0). To je vrijeme kada rade algoritmi koji veliki problem dijele na mnogo malih, a zatim, nakon što ih riješe, kombiniraju rješenja.
Funkcija složenosti 0(e N). Algoritmi s eksponencijalnom složenošću najčešće proizlaze iz pristupa koji se naziva brute force.
Funkcija složenosti 0(M) - broj operacija raste proporcionalno faktorijelu N.
Programer mora biti sposoban analizirati algoritme i odrediti njihovu složenost. Vremenska složenost algoritma može se izračunati na temelju analize njegovih upravljačkih struktura.
Algoritmi bez petlji i rekurzivnih poziva imaju konstantnu složenost. Ako nema rekurzije i petlji, sve upravljačke strukture mogu se svesti na strukture konstantne složenosti. Posljedično, cijeli algoritam također karakterizira stalna složenost. Određivanje složenosti algoritma uglavnom se svodi na analizu petlji i rekurzivnih poziva.
Na primjer, razmotrite algoritam za obradu elemenata niza.
Za /": = 1 do N učiniti Počnite
Složenost ovog algoritma OKO(A), budući da se tijelo petlje izvodi A puta, a složenost tijela petlje je 0(1). Ako je jedna petlja ugniježđena unutar druge i obje petlje ovise o veličini iste varijable, tada cijeli dizajn karakterizira kvadratna složenost.
Za /: = 1 do N učiniti Za j: = 1 do N učiniti Počnite
Složenost ovog programa 0(N 2).
Primjer 1. Procijenimo složenost programa koji s tipkovnice unese niz iu njemu pronađe najveći element. Algoritam se sastoji od sljedećih koraka:
- - unos niza (trebate pročitati A elemente);
- - traženje najvećeg elementa (potrebno je napraviti A - 1 usporedbu);
- - ispis rezultata (morate ispisati jedan broj ili niz).
Zbrojimo broj operacija A + (A - 1) + 1 = 2A, tj. postoji
takva konstanta da za bilo koji A broj operacija ne prelazi CA. Stoga je složenost algoritma 0(A).
Primjer 2. Procijenimo složenost programa koji s tipkovnice unese niz iu njemu pronađe element sa zadanim svojstvom (npr. jednak određenoj vrijednosti). Algoritam se sastoji od sljedećih koraka:
- - unos polja (Operacije unosa);
- - traženje elementa sa zadanim svojstvom (element se može nalaziti ili bliže početku niza ili na samom kraju; ako element ne postoji, tada se moraju napraviti sve A usporedbe kako bi se to uvjerilo);
- - izlaz rezultata.
U najboljem slučaju navedeni algoritam će zahtijevati A + 2 operacije (unos cijelog niza, jedna usporedba, izlaz), u najgorem slučaju (kada takvog elementa nema, 2A + 1 operacija). Ako je A velik broj, na primjer reda veličine 10 6, tada se jedinica može zanemariti. Stoga je složenost algoritma jednaka 0(N).
Primjer 3. Definirajmo funkciju složenosti algoritma za šifriranje za riječ duljine L metodom supstitucije. Neka postoji tablica u kojoj je za svaki znak abecede napisan znak kojim se mora zamijeniti. Označimo broj slova abecede S. Algoritam se sastoji od sljedećih koraka:
- - unos riječi (jedna operacija);
- - organizacija ciklusa:
- 1) za svaki znak pronađite njegovu zamjenu u tablici (ako tablica nije uređena i nema svojstva koja olakšavaju pretraživanje, tada će vam u najgorem slučaju trebati S operacije za jedan znak ako je traženi element na samom kraju);
- 2) izlaz pronađenog simbola;
- - kraj ciklusa.
Ukupan broj operacija 1 + (S+)L. U slučaju dovoljno velikih S I L jedinice se mogu zanemariti, a ispada da je funkcija složenosti zadanog algoritma O(S L).
Primjer 4. Definirajmo funkciju složenosti algoritma prevođenja prirodnih brojeva 1 V u binarni brojevni sustav (bez operacija unosa i izlaza podataka). Algoritam se sastoji od sljedećih koraka:
- - petlja dok rezultat dijeljenja broja s 2 ne bude jednak 0:
- - podijelite broj s 2 i zapamtite ostatak;
- - uzeti rezultat dijeljenja kao novi broj;
- - kraj ciklusa.
Ukupan broj operacija ne prelazi 1 + log 2 A. Stoga opisani algoritam ima složenost 0 (og 2 N).
