Ocena računske zahtevnosti. Časovna zahtevnost algoritma

Določanje kompleksnosti algoritma

Ocena funkcije kompleksnosti, dobljena z asimptotično analizo, se imenuje kompleksnost algoritma.

Upoštevati je treba, da obstaja več ocen kompleksnosti algoritma.

Asimptotično obnašanje funkcije kompleksnosti je operativna kompleksnost. Poleg tega lahko določite naslednje vrste težav.

Začasno kompleksnost - asimptotična ocena časa delovanja algoritma na vhodnih podatkih dolžine p. Očitno je, da v odsotnosti paralelizacije računalniških postopkov čas delovanja algoritma enolično določa število izvedenih operacij. Konstantni koeficienti, ki izražajo trajanje operacij, ne vplivajo na vrstni red časovne zahtevnosti, zato enačbi za operativno in časovno zahtevnost pogosto sovpadata.

kapacitivni kompleksnost - asimptotična ocena števila sočasno obstoječih skalarjev pri izvajanju algoritma na vhodnih podatkih dolžine p.

Strukturni kompleksnost - značilnost števila krmilnih struktur v algoritmu in posebnosti njihovega relativnega položaja.

kognitivne kompleksnost - značilnost razpoložljivosti algoritma za razumevanje s strani strokovnjakov na področjih uporabe.

Vrste in zapis asimptotike

Pri asimptotični analizi algoritmov je običajno uporabljati zapis matematične asimptotične analize. V tem primeru so upoštevane tri ocene (asimptotike) kompleksnosti algoritmov, ki jih označimo na naslednji način:

1) /(i) = O^(n))- asimptotično natančna ocena funkcije kompleksnosti /(«), oziroma operativne kompleksnosti algoritma;
2) /(n) = 0(§(n)) - asimptotično natančna zgornja ocena funkcije kompleksnosti /( p);
3) /(l) = ?2(#(l)) - asimptotično natančna spodnja ocena funkcije vloženega dela /( P).

Namesto imenovanja C1^(n)) zelo pogosto se preprostejši o(^(“)) uporablja z malo črko v kurzivu »o«.

Razložimo semantiko formul na primeru: če je zapisano / (n) = 0 (^2 (n)), POTEM TO pomeni, da funkcija g(n)=og2 (n) je asimptotično natančna ocena funkcije kompleksnosti /(«). Pravzaprav obstaja definicija dveh položajev v obliki trditve:

Če f(n)= @(log2(")),

mo g(n)\u003d log 2 (l) - asimptotično natančna ocena f(n).

Upoštevajte, da konstantni faktor ne vpliva na vrstni red kompleksnosti algoritma, zato je osnova logaritma pri podajanju logaritemske kompleksnosti izpuščena in preprosto zapišejo f(l) = @(lо§(l)), kar pomeni, da logaritem ima poljubno osnovo, večjo od ena.

Formalne definicije asimptotike

Asimptotično natančna ocena funkcije vložka dela z, z 2 , l 0 , tako da se pri l>l 0 funkcija /(l) do konstantnih faktorjev ne razlikuje od funkcije g( k), nato funkcijo g(n) imenujemo asimptotično natančna ocena funkcije /(k).

3 s ], s 2 e IN, z x > 0, z 2 > 0:
- (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l)),

kjer so 9^, N množice vseh realnih oziroma naravnih števil.

Asimptotično natančna zgornja meja za funkcijo kompleksnosti verbalno opredeljeno takole: če obstajajo pozitivna števila z in l 0 , tako da za l>l 0 funkcija /(l) ne raste hitreje kot funkcija g(n) do konstantnega faktorja c, potem funkcija g(n) imenujemo asimptotično natančna zgornja meja funkcije Ap).

Natančnejša formalna definicija ima obliko:

3 z e %s > 0:
- (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

Asimptotično natančna spodnja meja za funkcijo kompleksnosti verbalno opredeljeno takole: če obstajajo pozitivna števila z in l 0 , tako da za l>l 0 funkcija /(l) ne raste počasneje kot funkcija g(n) do konstantnega faktorja z, potem se funkcija?(k) imenuje asimptotično natančna spodnja meja za funkcijo

Natančnejša formalna definicija ima obliko:

3 z e 9^, z > 0:
- (3 i 0 e X, i 0 > 0: (/i e K, i > jaz 0: 0 s? g(n)

/(JAZ) = 0.^(n))

Upoštevajte naslednje:

1) neenakosti, navedene v formalnih definicijah asimptotike, v splošnem primeru ne morejo zadostiti ena, ampak določen niz funkcij, pogosto z neštetim nizom izrazov, tako da konstrukcije Q(g(n)), 0^(n)) in 0.^(n)) simbolizirajo nabor funkcij, s katerim primerjamo preiskovano funkcijo vloženega dela /(i); zaradi tega je v zapisu asimptotike oblike /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n )) namesto znaka "= » bi bilo bolj racionalno uporabiti znak "e";
2) modeli (d^(n)), 0^(n)) in ?1^(n)), ki se uporabljajo kot oznake za nekatere količine, je treba brati v skladu s tem, kot sledi: vsaka funkcija, ki je enaka, ne raste hitreje in ne raste počasneje g(n).

Sovpadanje in razlika asimptotik

Bodimo pozorni na naslednje dejstvo: ocena /(s) = 0(?(s)) postavlja zgornjo in spodnjo oceno za /(s), saj njena definicija predpostavlja veljavnost relacije c g g(n)

Naslednja lastnost asimptotike je povsem očitna: če ocena φ(n) = ©^(n)) obstaja, potem veljajo enakosti /( p) = 0(^(n)) in /(n) = ?2(#(n)), tj. zgornja in spodnja ocena delovne intenzivnosti sovpadata; če je /(i) = 0(? max (i)) in φ(n) = C1^ mn (n)), in g max (n)Фg m 1n(i), potem ni funkcije g(n), tako da je /(i) = 0(?(i)).

Sovpadanje zgornje in spodnje ocene delovne intenzivnosti je možno v naslednjih primerih:

1) funkcija kompleksnosti za vse vrednosti vhodne dolžine je deterministična (nenaključna) funkcija, tj. število izvedenih operacij ni odvisno od posebnosti začetnih vrednosti podatkov; takšne so na primer funkcije odvisnosti števila operacij množenja in deljenja od števila neznanih veličin v algoritmu za reševanje sistemov linearnih algebrskih enačb z metodo IS ekspanzije;
2) funkcija delovne intenzivnosti je naključna funkcija, tj. število izvedenih operacij je odvisno od posebnosti začetnih podatkov in (ali) vrstnega reda njihovega prejema in lahko določite funkcije / m | n (i), / max (i), ki opisujejo najmanjše in največje število operacije, ki jih izvede izvajalec algoritma za določeno vhodno dolžino i, vendar imata obe funkciji enake dominante, na primer, sta polinoma istega reda.

Ko gre za ocenjevanje vrstnega reda operativne kompleksnosti, je treba upoštevati tri pomembna pravila:

1) stalni dejavniki niso pomembni za določanje vrstnega reda zahtevnosti, tj. 0 (k? g(n)) = 0(g(")) ;
2) vrstni red kompleksnosti produkta dveh funkcij je enak produktu njunih kompleksnosti, saj velja enakost:
0(gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
3) vrstni red kompleksnosti vsote funkcij je enak vrstnemu redu prevladujočih členov, na primer: 0(i e + n 2 + n) = 0 (i 5).

Zgornja pravila uporabljajo simbol samo ene asimptotike 0("), vendar veljajo za vse asimptotične ocene - in za 0( ) , in &.{ ).

v množici elementarne funkcije lahko določite seznam funkcionalne prevlade: če -spremenljivka, a,b- numerične konstante, potem veljajo naslednje trditve: i" dominira i!; i! dominira a"; a" prevladuje Zj" če a>b a str prevladuje p b, če a> 1 za katero koli b e 9? ; n a prevladuje a/ če a>b i prevladuje nad log q(i), če a > 1.

Ocena povprečne delovne intenzivnosti

V praksi, re Pri računalniških izračunih je zelo zanimivo oceniti f(n) matematičnega pričakovanja kompleksnosti M, saj je v veliki večini primerov f(n) naključna funkcija. Vendar pa se v procesu eksperimentalnih študij algoritmov z naključnim /(n) pojavi dodatna težava - izbira števila poskusov za zanesljivo oceno M. Premagovanje tega problema je osrednja naloga v . Predlagana rešitev temelji na uporabi porazdelitve beta za aproksimacijo /(n). To je zelo konstruktivna in vsestranska tehnika. Vendar pa je v sodobnih razmerah, ko je zmogljivost računalnika precej visoka, v mnogih primerih mogoče uporabiti preprostejšo metodo za izbiro obsega testov, ki temelji na spremljanju trenutne variabilnosti vrednosti. f(n) - vrednosti se ocenjujejo, dokler varianca ocen ne postane manjša od navedene napake.

Ocenjevanje operativne kompleksnosti algoritma

Kompleksnost algoritma je mogoče določiti na podlagi analize njegovih nadzornih struktur. Algoritmi brez zank in rekurzivnih klicev imajo stalno kompleksnost. Zato se definicija kompleksnosti algoritma zmanjša predvsem na analizo ciklov in rekurzivnih klicev.

Razmislite o algoritmu za brisanje do-th element iz niza velikosti p, sestavljen iz premikanja elementov matrike iz (na + 1) -th do p- pojdite za en položaj nazaj na začetek matrike in zmanjšajte število elementov p na enoto. Kompleksnost zanke obdelave polja je Oh (p-k), ker se izvaja telo zanke (operacija premikanja). PC krat, kompleksnost telesa zanke pa je 0(1), tj. je stalnica.

V obravnavanem primeru je kompleksnost označena z asimptotiko 0("), saj število operacij, izvedenih v tem algoritmu, ni odvisno od posebnosti vrednosti podatkov. Funkcija kompleksnosti je deterministična in vse vrste asimptotik med seboj sovpadajo: f(n) = Q(n-k), f(n) = 0(n-k) in f(n) = Q(n- do). To dejstvo dokazuje navedba točno ©( ). Uporabite 0(*) in/ali?2(*) le, če se ti asimptotiki razlikujeta.

Vrsta zanke (for, while, repeat) ne vpliva na kompleksnost. Če je ena zanka ugnezdena v drugo in sta obe zanki odvisni od velikosti iste spremenljivke, je za celotno konstrukcijo značilna kvadratna kompleksnost. Gnezdenje ponavljanj je glavni dejavnik pri rasti kompleksnosti. Kot primer predstavljamo zapletenost dobro znanih algoritmov iskanja in razvrščanja za niz velikosti P:

število primerjalnih operacij pri zaporednem iskanju: 0(n);
število primerjalnih operacij v binarnem iskanju: 0 (log 2 p);
število primerjalnih operacij pri metodi preproste menjave (razvrščanje z mehurčki): 0(n 2);
število permutacijskih operacij pri razvrščanju z mehurčki: 0 (n 2);

Upoštevajte, da ima število primerjalnih operacij v metodi preproste izmenjave asimptotiko 0 (n 2), število permutacijskih operacij pa ima dve različni asimptotiki 0(str 2) in?2(0), ker število primerjav ni odvisno od specifičnosti vrednosti razvrščenih podatkov, medtem ko je število permutacij določeno s to specifičnostjo. Permutacije morda sploh ne bodo izvedene - če je niz podatkov na začetku pravilno urejen ali pa je število permutacij največje - vrstnega reda p 2 , - če je razvrščeni niz prvotno urejen v nasprotni smeri.

Ime funkcije g(n) v asimptotiki /(x) = @(x(x)) in /(a) = 0(g(n)) funkcija kompleksnosti /(«) se uporablja za karakterizacijo algoritma. Tako govorimo o algoritmih polinomske, eksponentne, logaritemske itd. kompleksnosti.

Zagotovo ste pogosto naleteli na oznake, kot je O (log n), ali slišali besedne zveze, kot je "logaritemska računska kompleksnost" v zvezi s katerim koli algoritmom. In če še vedno ne razumete, kaj to pomeni, je ta članek za vas.

Ocena težavnosti

Kompleksnost algoritmov se običajno ocenjuje s časom izvajanja ali s porabljenim pomnilnikom. V obeh primerih je kompleksnost odvisna od velikosti vhodnih podatkov: matrika 100 elementov bo obdelana hitreje kot podobna 1000 elementov. Hkrati malo ljudi skrbi točen čas: odvisno je od procesorja, tip podatkov, programski jezik in številni drugi parametri. Pomembna je samo asimptotična kompleksnost, tj. kompleksnost, saj se velikost vhoda nagiba k neskončnosti.

Recimo, da mora neki algoritem izvesti 4n 3 + 7n pogojnih operacij za obdelavo n vhodnih podatkovnih elementov. Ko se n poveča, bo na skupni čas delovanja bistveno bolj vplivalo povišanje n na kocko kot pa množenje s 4 ali dodajanje 7n. Potem rečemo, da je časovna kompleksnost tega algoritma enaka O(n 3) , tj. kubično odvisna od velikosti vhodnih podatkov.

Uporaba velike črke O (ali tako imenovani O-zapis) izhaja iz matematike, kjer se uporablja za primerjavo asimptotičnega obnašanja funkcij. Formalno O(f(n)) pomeni, da čas delovanja algoritma (ali količina zasedenega pomnilnika) raste glede na količino vhodnih podatkov ne hitreje kot neka konstanta, pomnožena s f(n).

Primeri

O(n) - linearna kompleksnost

Takšno kompleksnost ima na primer algoritem za iskanje največjega elementa v nerazvrščenem nizu. Pregledati moramo vseh n elementov niza, da ugotovimo, kateri je največji.

O(log n) - kompleksnost dnevnika

Najenostavnejši primer je binarno iskanje. Če je matrika razvrščena, lahko preverimo, ali vsebuje določeno vrednost, tako da jo razpolovimo. Preverimo srednji element, če je večji od želenega, potem zavržemo drugo polovico niza - zagotovo ga ni. Če manj, potem obratno - začetno polovico zavržemo. In tako bomo še naprej delili na pol, posledično bomo preverili log n elementov.

O(n 2) - kvadratna kompleksnost

Takšno kompleksnost ima na primer algoritem za razvrščanje z vstavljanjem. V kanonični izvedbi je sestavljen iz dveh ugnezdenih zank: ena za prehod skozi celotno matriko in druga za iskanje mesta za naslednji element v že razvrščenem delu. Tako bo število operacij odvisno od velikosti matrike kot n * n, tj. n 2 .

Obstajajo tudi druge stopnje težavnosti, vendar vse temeljijo na istem principu.

Zgodi se tudi, da čas delovanja algoritma sploh ni odvisen od velikosti vhodnih podatkov. Nato je kompleksnost označena kot O(1) . Če želite na primer določiti vrednost tretjega elementa matrike, si elementov ni treba zapomniti ali jih večkrat prebrati. Vedno morate samo počakati na tretji element v vhodnem podatkovnem toku in to bo rezultat, katerega izračun za poljubno količino podatkov traja enako časa.

Podobno se vrednotenje izvaja po spominu, kadar je to pomembno. Vendar pa lahko algoritmi porabijo bistveno več pomnilnika, ko se velikost vnosa poveča kot drugi, vendar še vedno delujejo hitreje. In obratno. To pomaga izbrati najboljše načine za reševanje problemov glede na trenutne razmere in zahteve.

Termin: 8. januar 2010

Članka pred iztekom roka ne smejo urejati drugi udeleženci projekta Spletna stran. Na koncu ima vsak udeleženec pravico, da ta članek po lastni presoji popravi in izbriše to opozorilo, prikazano s predlogo ((Naloga)).

Poglej tudi smernice o uporabi vira Spletna stran v izobraževalnem procesu.

Teorija računske kompleksnosti Veja računalniške teorije, ki proučuje količino dela, potrebnega za rešitev računalniškega problema.

Naloga se šteje za težko, če rešitev problema zahteva veliko sredstev, ne glede na algoritem, uporabljen za rešitev. Teorija formalizira to intuitivno predstavo z uvedbo matematičnih modelov računanja za preučevanje teh problemov in kvantificiranje količine virov, potrebnih za njihovo rešitev, kot sta poraba časa in pomnilnika. Možna so tudi druga merila kompleksnosti, kot so: število sporočil (kompleksnost komunikacije), število elementov v vezju od funkcionalni elementi(zapletenost vezja) in število procesorjev. Predvsem teorija kompleksnosti računanja opredeljuje praktične omejitve glede tega, kaj računalniki lahko in česa ne.

S teorijo računske kompleksnosti je tesno povezana analiza algoritmov in teorija izračunljivosti. Glavna razlika med teorijo računske kompleksnosti in analizo algoritmov je v tem, da se slednja ukvarja z analizo količine virov, ki jih določen algoritem potrebuje za rešitev problema, medtem ko prva postavlja bolj splošno vprašanje o vseh možnih algoritmih, ki jih je mogoče uporabiti za rešiti isti problem. problem. Natančneje, teorija računalniške kompleksnosti poskuša razvrstiti probleme, ki jih je mogoče ali ne rešiti z ustrezno količino omejenih virov. Uvedba omejitev razpoložljivih virov pa je tisto, kar razlikuje teorijo računalniške kompleksnosti od teorije izračunljivosti: slednja se sprašuje, katere probleme je načeloma mogoče rešiti algoritemsko brez omejitve računalniških virov.

Računalniške težave

Primerki opravil

Računske probleme (naloge) lahko gledamo kot neskončno množico parov: (primer problema, rešitev za dani primer). Vhodni niz za računsko težavo je niz, ki opisuje primer težave. Izhodni niz za računski problem je opis rešitve za primer problema, ki ga opisuje vhodni niz. Na primer, problem prepoznavanja praštevila: primerek problema je število, za katerega je treba ugotoviti, ali je praštevilo ali ne, rešitev je niz »da«, če je to število praštevilo in »ne "drugače. Teorija računalniške kompleksnosti obravnava le velike probleme, tj. zahteva, da je niz instanc nalog neskončen, je obvezna.

Pogled opravil

Pri obravnavanju računalniških problemov je opis primerka problema niz nad abecedo. Praviloma se abeceda šteje za binarno (tj. množica (0,1)). Različni matematični objekti morajo biti ustrezno kodirani. Tako so lahko na primer cela števila predstavljena v binarni sistem računanje, grafe pa je mogoče kodirati neposredno glede na njihove matrike sosednosti ali prek njihovega kodiranja seznamov sosednosti v dvojiški obliki.

Naloge za prepoznavanje

Problem prepoznavanja je eden osrednjih predmetov preučevanja v teoriji računalniške kompleksnosti. Naloga za prepoznavanje je posebna vrsta računskega problema, katerega odgovor je "da" ali "ne" (1 ali 0). Problem prepoznavanja lahko formuliramo kot problem, ali vhodni niz pripada določeni podmnožici (jeziku) množice vseh vhodnih nizov. Vhodni niz težave pripada ustreznemu jeziku, če in samo če je odgovor na ta niz "da". Tako je naloga prepoznavanja naloga prepoznavanja, da vhodni niz pripada določenemu jeziku.

Primer težave s prepoznavanjem. Vhodni niz: opis poljubnega grafa. Težava je ugotoviti, ali je dani graf povezan ali ne. Jezik povezanih grafov je niz opisov vseh povezanih grafov. Da bi dobili natančno definicijo tega jezika, se moramo odločiti, kako so grafi kodirani kot binarni nizi.

Iskalne naloge

Iskalna naloga je računska naloga, pri kateri je izhodna vrednost bolj zapletena kot pri nalogi prepoznavanja (to pomeni, da ni samo "da" ali "ne").

Primer iskalnega problema je problem trgovskega potnika. Problem trgovskega potnika je eden najbolj znanih problemov kombinatorne optimizacije. Naloga je najti najbolj donosno pot, ki vsaj enkrat poteka skozi navedena mesta in se nato vrne v prvotno mesto. V pogojih problema je navedeno merilo donosnosti poti (najkrajša, najcenejša, kumulativno merilo itd.) In ustrezne matrike razdalj, stroškov itd.. Praviloma je navedeno, da mora pot potekati skozi vsako mesto samo enkrat - v tem primeru se izbira med Hamiltonovimi cikli. Vhodni niz: opis uteženega (tj. s številskimi oznakami na robovih) grafa. Izhodni niz je opis optimalne poti trgovskega potnika.

Med nalogami prepoznavanja in nalogami iskanja obstaja razmerje v paru. Problem iskanja lahko formuliramo kot problem prepoznavanja. Na primer, za iskalni problem "množenje dveh števil" lahko ustrezen problem prepoznavanja para predstavimo kot niz trojk (A, B, C), tako da je razmerje A × B = C izpolnjeno.

Težavnost merjenja

Teorija računalniške kompleksnosti je nastala iz potrebe po primerjavi hitrosti algoritmov, jasno opisati njihovo vedenje (čas izvajanja, obseg potreben pomnilnik itd.), odvisno od velikosti dovoda in odvoda.

Število elementarnih operacij, ki jih algoritem porabi za rešitev določenega primera problema, ni odvisno le od velikosti vhodnih podatkov, temveč tudi od samih podatkov. Na primer, število operacij algoritma za razvrščanje z vstavljanjem je veliko manjše, če so vhodni podatki že razvrščeni. Da bi se izognili takšnim težavam, upoštevajte koncept časovne kompleksnosti algoritma v najslabšem primeru.

Časovna kompleksnost algoritma (v najslabšem primeru) je funkcija velikosti vhodnih in izhodnih podatkov, ki je enaka največjemu številu elementarnih operacij, ki jih izvede algoritem za rešitev primerka problema določene velikosti. Pri problemih, kjer velikost izhoda ne presega ali je sorazmerna z velikostjo vhoda, lahko časovno kompleksnost obravnavamo samo kot funkcijo velikosti vhodnih podatkov.

Podobno kot pojem časovne zahtevnosti v najslabšem primeru je definiran pojem časovne zahtevnosti algoritma v najboljšem primeru. Upoštevajte tudi koncept povprečnega časa delovanja algoritma, to je matematično pričakovanje časa delovanja algoritma. Včasih se preprosto reče: "Časovna kompleksnost algoritma" ali "Čas algoritma", kar se nanaša na časovno kompleksnost algoritma v najslabšem, najboljšem ali povprečnem primeru (odvisno od konteksta).

Po analogiji s časovno kompleksnostjo določajo prostorsko kompleksnost algoritma, le da tukaj ne govorimo o številu elementarnih operacij, temveč o količini uporabljenega pomnilnika.

Kljub temu, da je funkcijo časovne kompleksnosti algoritma v nekaterih primerih mogoče natančno določiti, je v večini primerov nesmiselno iskati njeno točno vrednost. Dejstvo je, da je, prvič, natančna vrednost časovne kompleksnosti odvisna od definicije elementarnih operacij (kompleksnost lahko na primer merimo v številu aritmetičnih operacij ali operacij na Turingovem stroju), in drugič, kot velikost vhodni podatki se povečajo, prispevek konstantnih faktorjev in členov nižjih redov, ki se pojavljajo v izrazu za natančen obratovalni čas, postane skrajno nepomemben.

Upoštevanje vhodnih podatkov velika številka in ocena vrstnega reda rasti časa izvajanja algoritma vodita do koncepta asimptotične kompleksnosti algoritma. Hkrati je algoritem z manjšo asimptotično kompleksnostjo bolj učinkovit za vse vhodne podatke, razen morda za podatke majhne velikosti.

Kompleksnost se določi na podlagi računalniškega modela, v katerem se izvajajo izračuni.

Računalniški modeli

Obstaja veliko različnih modelov računalništva: Post stroj, Minskyjev stroj, lambda račun, delno rekurzivne funkcije, običajni Markovljevi algoritmi, stroji z naključnim dostopom do pomnilnika (RAM stroji) itd. Omenimo le najbolj priljubljen računalniški model - Turingov stroj.

Turingov stroj

Turingov stroj (MT) je abstraktni izvajalec (abstraktni računalnik). Predlagal ga je Alan Turing leta 1936, da bi formaliziral koncept algoritma.

Turingov stroj je razširitev končnega avtomata in je v skladu s Church-Turingovo tezo sposoben posnemati vse druge izvajalce (s podajanjem prehodnih pravil), ki na nek način izvajajo postopek izračuna po korakih, v katerem vsak izračun korak je precej elementaren.

Sestava Turingovega stroja vključuje trak, ki je neskončen v obe smeri (možni so Turingovi stroji, ki imajo več neskončnih trakov), razdeljen na celice in krmilno napravo, ki je sposobna biti v enem od mnogih stanj. Število možnih stanj krmilne naprave je končno in natančno podano.

Krmilna naprava se lahko premika levo in desno po traku, bere in piše simbole neke končne abecede v celice traku. Dodeljen je poseben prazen simbol, ki zapolni vse celice traku, razen tistih (končno število), na katerih so zapisani vhodni podatki.

Krmilna naprava deluje po pravilih prehoda, ki predstavljajo algoritem, ki ga izvaja ta Turingov stroj. Vsako prehodno pravilo ukaže stroju, da glede na trenutno stanje in simbol, opažen v trenutni celici, zapiše nov simbol v to celico, gre v novo stanje in premakne eno celico v levo ali desno. Nekatera stanja Turingovega stroja lahko označimo kot terminalna, prehod v katero koli od njih pa pomeni konec dela, zaustavitev algoritma.

Za Turingov stroj pravimo, da je determinističen, če vsaka kombinacija stanja in simbola traku v tabeli ustreza največ enemu pravilu. Če obstaja par (simbol traku - stanje), za katerega obstajata 2 ali več navodil, se tak Turingov stroj imenuje nedeterminističen.

Model Turingovega stroja omogoča različne razširitve. Upoštevamo lahko Turingove stroje s poljubnim številom trakov in večdimenzionalne trakove z različnimi omejitvami; stroji, ki uporabljajo vir naključnosti.

Turingov stroj je eden glavnih modelov računanja v teoriji kompleksnosti.

Težavnostni razredi

Kompleksni razredi so množice računskih problemov, ki so po računski zahtevnosti približno enaki. Obstajajo jezikovni kompleksni razredi in funkcionalni kompleksni razredi. Razred kompleksnosti jezikov je nabor predikatov (funkcij, ki sprejmejo besedo kot vhod in vrnejo odgovor 0 ali 1), ki za izračun uporabljajo približno enako količino virov. Koncept razreda funkcionalne kompleksnosti je podoben, le da ne gre za niz predikatov, ampak za niz funkcij. V teoriji kompleksnosti je razred kompleksnosti privzeto razred kompleksnosti jezikov. Tipična definicija razreda kompleksnosti izgleda takole:

Kompleksni razred X je niz predikatov P(x), ki so izračunljivi na Turingovih strojih in za računanje uporabljajo vir O(f(n)), kjer je n dolžina besede x.

Viri se običajno vzamejo kot računski čas (število delovnih ciklov Turingovega stroja) ali delovno območje (število celic, uporabljenih na traku med delovanjem). Istemu razredu naj bi pripadali tudi jeziki, ki jih prepoznajo predikati iz določenega razreda (to je nabor besed, za katere predikat vrne 1).

Poleg tega je veliko razredov mogoče opisati tudi v smislu matematične logike ali teorije iger.

Razredi so običajno označeni z velikimi črkami. Komplement razreda C (to je razred jezikov, katerih komplementi pripadajo C) je označen kot co-C.

Za vsak razred obstaja kategorija nalog, ki so »najtežje«. To pomeni, da je vsaka naloga iz razreda reducirana na takšno nalogo, poleg tega pa je naloga sama v razredu. Takšni problemi se imenujejo popolni problemi za dani razred.

Razred P

Razred P (iz angleščine polynomial) - niz problemov prepoznavanja, ki jih je mogoče rešiti na determinističnem Turingovem stroju v polinomskem času na dolžino vhoda. Podobno je za težave pri iskanju definiran razred FP (iz angleškega funkcionalnega polinoma).

Bolj formalno, razmislite o determinističnih Turingovih strojih, ki izračunajo odgovor glede na besedo na vhodnem traku iz vhodne abecede. Čas delovanja Turingovega stroja za fiksno vhodno besedo x je število delovnih ciklov Turingovega stroja od zagona do zaustavitve stroja. Kompleksnost funkcije, ki jo izračuna Turingov stroj, je funkcija, ki je odvisna od dolžine vhodne besede in je enaka največjemu času delovanja stroja v vseh vhodnih besedah fiksne dolžine:

Če za funkcijo f obstaja Turingov stroj M tako, da za neko število c in dovolj velika n, potem pravimo, da pripada razredu FP ali je polinomska v času.

Razred P je eden temeljnih v teoriji računske kompleksnosti.

razred NP

Razred NP (iz angleškega non-deterministic polynomial) je niz problemov razpoznavanja, katerih čas rešitve je bistveno odvisen od velikosti vhodnih podatkov; hkrati pa obstaja algoritem, ki lahko, ko poleg opisa vhodnih vrednosti prejme še nekaj dodatnih informacij (priča o rešitvi), dovolj hitro (v času, ki ne presega polinoma velikosti podatkov) reši težava.

Bolj formalno velja, da jezik L pripada razredu NP, če obstaja dvomestni predikat R(x, y) iz razreda P (to je izračunljiv v polinomskem času) in polinom p, tako da za katero koli besedo x dolžine n je pogoj "x pripada L" enakovreden pogoju "obstaja y dolžine manjše od p(n), tako da je R(x, y) resničen". Beseda y se imenuje priča, da x pripada jeziku L. Torej, če imamo besedo, ki pripada jeziku, in drugo besedo-pričo omejene dolžine (ki jo je težko najti), potem lahko hitro preverimo, da x res pripada L. Vsak problem, ki pripada NP, je mogoče rešiti v eksponentnem času s preštevanjem vseh možnih prič z dolžino, manjšo od p(n).

Primer problema iz NP: problem prepoznavanja "Obstoj celoštevilske rešitve sistema linearnih neenačb." Priča je rešitev sistema neenačb. V polinomskem času je enostavno preveriti, ali prisotna rešitev ustreza.

Razred NP vključuje razred P.

Odprta vprašanja

V teoriji računske kompleksnosti je veliko nerešenih problemov, ki zadevajo predvsem vprašanja ločevanja ali gnezdenja določenih kompleksnih razredov. Eno od teh vprašanj je problem enakosti razredov P in NP.

Problem enakosti razredov P in NP

Navsezadnje je problem enakosti razredov P in NP naslednji: če je mogoče pozitiven odgovor na vprašanje hitro preveriti (v polinomskem času), potem je res, da je odgovor na to vprašanje mogoče hitro najti (v polinomskem času) )?

Iz definicije razredov P in NP takoj sledi posledica: . Vendar pa zaenkrat ni nič znanega o strogosti te vključitve, tj. ali obstaja algoritem, ki je v NP, vendar ne v P. Če takega algoritma ni, potem je mogoče vse probleme, ki pripadajo razredu NP, rešiti v polinomskem času, kar obljublja ogromno računsko korist. Zdaj je najtežje NP-probleme (tako imenovane NP-komplete probleme) mogoče rešiti v eksponentnem času, kar je skoraj vedno nesprejemljivo.

Vprašanje enakosti teh dveh razredov velja za enega najtežjih odprtih problemov na področju teoretičnega računalništva. Trenutno večina matematikov meni, da ti razredi niso enaki. Clay Mathematics Institute je to težavo uvrstil na svoj seznam problemov tisočletja in ponudil milijon dolarjev nagrade za njeno rešitev.

Literatura

Gehry M., Johnson D. Računalniški stroji in težko rešljivi problemi. Založba Mir leta 1982. - 420 str. Monografija ameriških znanstvenikov je posvečena reševanju kompleksnih (vključno z NP-težkimi) kombinatoričnih problemov, ki se pojavljajo pri diskretni optimizaciji, matematičnem programiranju, algebri, teoriji avtomatov s primeri.
Kormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford Algorithms: konstrukcija in analiza, 2. izdaja = Introduction to Algorithms second edition. - M.: "Williams", 2005. -

Vemo že, da pravilnost še zdaleč ni edina kvaliteta, ki bi jo moral imeti dober program. Eden najpomembnejših je učinkovitost, ki je značilna predvsem za dobavni rok programi za različne vhodne podatke (parameter ).

Iskanje natančne odvisnosti za določen program je precej težka naloga. Zaradi tega je običajno omejen asimptotične ocene to funkcijo, to je opis njenega približnega obnašanja za velike vrednosti parametra. Včasih se za asimptotične ocene uporablja tradicionalna relacija (beri "Big O") med dvema funkcijama , katere definicijo je mogoče najti v katerem koli učbeniku o matematični analizi, čeprav se pogosteje uporablja ekvivalenčno razmerje(beri "theta big"). Njegova formalna definicija je na primer v knjigi, čeprav bo za zdaj dovolj, da to vprašanje razumemo na splošno.

Kot prvi primer se vrnimo k programom, ki smo jih pravkar obravnavali za iskanje faktoriala števila. Zlahka je videti, da je število operacij, ki jih je treba izvesti, da bi našli faktorijel ! število v prvem približku je premo sorazmerno s tem številom, ker je število ponovitev cikla (iteracij) v tem programu enako . V takšni situaciji je običajno reči, da ima program (ali algoritem). linearna kompleksnost(zapletenost oz.).

Ali je možno faktorial izračunati hitreje? Izkazalo se je, da. Možno je napisati program, ki bo dal pravilen rezultat za iste vrednosti, za katere to storijo vsi zgornji programi, brez uporabe iteracije ali rekurzije. Njegova kompleksnost bo , kar pravzaprav pomeni organizacijo izračunov po neki formuli brez uporabe ciklov in rekurzivnih klicev!

Nič manj zanimiv ni primer izračuna Fibonaccijevega števila. V procesu njenega preučevanja se je namreč že ugotovilo, da je njena kompleksnost eksponentno in enako . Takšni programi v praksi praktično niso uporabni. To je zelo enostavno preveriti tako, da z njim poskušate izračunati 40. Fibonaccijevo število. Zaradi tega je naslednji problem precej aktualen.

Naloga 5.4 linearna kompleksnost.

Tukaj je rešitev tega problema, v kateri spremenljivki j in k vsebujeta vrednosti dveh zaporednih Fibonaccijevih števil.

Besedilo programa

javni razred FibIv1 ( javni statični void main(String args) vrže izjemo ( int n = Xterm.inputInt("Vnesite n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); ) ) )

Naslednje vprašanje je povsem naravno - ali je mogoče najti Fibonaccijeva števila še hitreje?

Po študiju določenih delov matematike je precej preprosto izpeljati naslednjo formulo za -to Fibonaccijevo število, ki jo je enostavno preveriti za majhne vrednosti:

Morda se zdi, da je na njegovi podlagi enostavno napisati kompleksen program, ki ne uporablja ponavljanja ali rekurzije.

Besedilo programa

javni razred FibIv2 ( javni statični void main(String args) vrže izjemo ( int n = Xterm.inputInt("Vnesite n -> "); dvojno f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0,5); Xterm.println("f(" + n + ") = " + j); ) )

Pravzaprav ta program uporablja klic funkcije potenciranja ( Math.pow(f,n) ), ki je ni mogoče izvesti hitreje kot v logaritemskem času (). O algoritmih, pri katerih je število operacij približno sorazmerno (v računalništvu je navada, da ne navajajo osnove binarnega logaritma), pravijo, da imajo logaritemska kompleksnost ().

Za izračun Fibonaccijevega števila obstaja takšen algoritem, katerega programsko izvedbo bomo podali brez dodatnih komentarjev, sicer boste morali preveč razložiti (povezava Fibonaccijevih števil s potencami določene matrike drugega reda, uporaba razredov za delo z matrikami, algoritem za hitro dvigovanje matrike na potenco) .

Naloga 5.5. Napišite program, ki izpiše -to Fibonaccijevo število, ki ima logaritemska kompleksnost.

Besedilo programa

javni razred FibIv3 ( javni statični void main(String args) vrže izjemo ( int n = Xterm.inputInt("Vnesite n -> "); Xterm.print("f(" + n + ")"); if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) (if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " +b.fib()); ) ) ) Matrika razreda ( zasebni dolgi a, b, c, d; javna matrika ( dolgi a, dolgi b, dolgi c, dolgi d) ( this.a = a; this.b = b; this.c = c; this.d = d; ) public void mul(Matrix m) ( long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+ d *m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; ) public void square() ( mul(this); ) public long fib( ) ( vrni b; ) )

Če poskušate izračunati desetmilijonto Fibonaccijevo število s tem in prejšnjim programom, bo razlika v času izračuna precej očitna. Na žalost bo rezultat napačen (v obeh primerih) zaradi omejenega obsega števil tipa long .

V zaključku podajamo primerjalno tabelo izvajalnih časov algoritmov različnih zahtevnosti in pojasnjujemo, zakaj se z večanjem hitrosti računalnika bistveno povečuje pomen uporabe hitrih algoritmov.

Razmislite o štirih algoritmih za reševanje istega problema s kompleksnostjo , , oziroma . Recimo, da drugi od teh algoritmov zahteva točno eno minuto časa, da se izvede na nekem računalniku z vrednostjo parametra. Potem bodo časi izvajanja vseh teh štirih algoritmov na istem računalniku z različnimi vrednostmi parametra približno enaki kot v 10 300000 letih

Ko programerji začetniki testirajo svoje programe, so vrednosti parametrov, od katerih so odvisni, običajno majhne. Torej, tudi če je bil pri pisanju programa uporabljen neučinkovit algoritem, lahko to ostane neopaženo. Vendar, če podoben program poskusite uporabiti v realnih pogojih, potem se bo njegova praktična neprimernost takoj pokazala.

S povečanjem hitrosti računalnikov se povečajo tudi vrednosti parametrov, za katere se delovanje enega ali drugega algoritma zaključi v sprejemljivem času. Tako se poveča povprečna vrednost vrednosti in posledično se poveča vrednost razmerja časov izvajanja hitrega in počasnega algoritma. kako hitrejši računalnik, večja je relativna izguba pri uporabi slabega algoritma!

Za primerjavo algoritmov je običajno uporabiti splošno karakteristiko, imenovano učinkovitost. Rečeno je, da je algoritem L, bolj učinkovit algoritem A 2,če algoritem L, teče v krajšem času in (ali) zahteva manj računalniški viri (pomnilnik z naključnim dostopom, prostor na disku, omrežni promet itd.).

Učinkovit algoritem mora izpolnjevati zahteve po sprejemljivem času izvajanja in razumni porabi virov, kot je že omenjeno v razdelku 1.1. Kombinacija teh značilnosti je koncept kompleksnosti algoritma. S povečanjem časa izvajanja algoritma in (ali) vključenih virov se kompleksnost poveča. Tako sta koncepta učinkovitosti in kompleksnosti nasprotna drug drugemu.

Značilnost algoritma, ki odraža čas, porabljen za njegovo izvajanje, se imenuje časovna kompleksnost. Značilnost algoritma, ki odraža stroške računalniških virov njegovega izvajanja, se imenuje kapacitivna kompleksnost.

Pri kvantitativnem in kvalitativnem ocenjevanju algoritma, povezanega z določanjem kompleksnosti, se uporabljata dva pristopa - praktični in teoretični.

Praktični pristop povezana z dejanskim izvajanjem algoritmov na določenih fizične naprave. Zanj so značilni parametri, ki jih je mogoče izmeriti in določiti. Časovna kompleksnost pri tem pristopu se lahko izrazi v časovnih enotah (npr. milisekundah) ali številu procesorskih ciklov, potrebnih za izvedbo algoritma. Kapacitivno kompleksnost je mogoče izraziti v bitih (ali drugih enotah informacij), minimalnih strojnih zahtevah, potrebnih za izvajanje algoritma itd.

Praktični rezultat ni absolutno merilo uspešnosti algoritma. Kvantitativne vrednosti, dobljene s tem pristopom, so odvisne od številnih dejavnikov, kot so:

specifikacije komponente, ki sestavljajo računalniški sistem. Torej, višja kot je urna frekvenca procesorja, več elementarnih operacij je mogoče izvesti na enoto časa;
značilnosti programskega okolja (število tekočih procesov, algoritem načrtovalca opravil, funkcije dela operacijski sistem itd.);
izbrani programski jezik za izvedbo algoritma. Program, napisan v jeziku na visoki ravni, bo verjetno deloval počasneje in zahteval več virov kot program, napisan v jezikih na nizki ravni, ki ima neposreden dostop do virov strojne opreme;
izkušnje programerja, ki je implementiral algoritem. Najverjetneje bo programer začetnik napisal manj učinkovit program kot izkušen programer.

Tako se algoritem izvaja v istem računalniški sistem za iste vhodne podatke ima lahko različne kvantitativne ocene v različnih časovnih točkah. Zato je pomembnejši teoretični pristop k opredelitvi kompleksnosti.

Teoretična kompleksnost opisuje algoritem brez sklicevanja na specifično strojno opremo, programsko opremo in orodja za implementacijo. V tem primeru je časovna zahtevnost izražena s številom operacij, ciklov Turingovega stroja ipd. Kapacitivno kompleksnost določa količina podatkov (vhodni, vmesni, izhodni), število vključenih celic na traku Tyoringovega stroja ipd.

V teoretičnem pristopu k oceni učinkovitosti velja, da se algoritem izvaja na nekaterih idealiziran računalnik, za katere je čas izvajanja vsake vrste operacije znan in konstanten. Menijo tudi, da so viri takega računalnika neskončni, zato kapacitivna kompleksnost v teoretičnem pristopu običajno ni določena. Kot časovno karakteristiko kompleksnosti je izbrano število ukazov (operacij), izvedenih na idealiziranem računalniku.

Kvantitativne ocene, pridobljene s teoretičnim pristopom, so lahko odvisne tudi od številnih naslednjih dejavnikov:

količino vhodnih podatkov. Večji ko je, več časa bo trajalo za izvedbo algoritma;
izbrani način reševanja problema. Na primer, za veliko količino vhodnih podatkov je algoritem hitrega razvrščanja učinkovitejši od algoritma mehurčkovega razvrščanja, čeprav vodi do enakega rezultata.

Čas izvajanja algoritma je običajno odvisen od količine vhodnih podatkov (input size), ki jo razumemo kot dimenzijo problema, ki ga rešujemo. Torej, pri razvrščanju niza vrednosti je količina podatkov število elementov tega niza. Pri obdelavi nizov je velikost vhodnih podatkov dolžina niza.

Pustiti P - količina vhodnih podatkov za neki algoritem. Označimo z T(p)število ukazov, izvedenih na idealiziranem računalniku med izvajanjem algoritma, in je določeno za "najslabši primer", ko je obseg operacij največji.

Koncept "najslabšega primera" lahko ponazorimo s primerom. Naj razmislimo o algoritmu za preverjanje prisotnosti numeričnega elementa v nekem nizu (nizu) števil. Če je ta niz razvrščen v naraščajočem vrstnem redu, potem na splošno nima smisla preverjati elementov, ki se nahajajo za prvim elementom, ki je večji od želenega. V tem primeru T(p) n. V najslabšem primeru (za poljubno nesortirano množico) pa boste morali pregledati vse elemente množice. Očitno tukaj T(n) = n.

Na splošno, T(p) je neka funkcija velikosti vhodnih podatkov p. V mnogih primerih T(p) izraženo kot polinom, potenca ali logaritemska funkcija p.

Vrednostno vedenje T(p) odvisno od povečave p klical asimptotična kompleksnost algoritem. To pravijo T(n) Ima vrstni red kompleksnosti 0(J(n))(preberi "O velik od/iz P") za nek algoritem, če obstaja konstanta z in količino podatkov sch tako da Yn > n 0 in obstaja neenakost T(n) s/(n).

To dejstvo je zapisano kot T(n) = 0(J(n)) in pomeni, da za funkcijo T(p) obstaja taka funkcija f(n) in konstantno с, za katero, začenši z nekaj n 0 , pomen T(p) ne presega cf(n).

funkcija f(n) predstavlja zgornjo mejo vrednosti funkcije T(n). Naj npr. T(n) = 2p A + n 2 . Z izbiro vrednot n 0= 0 in c = 5, za katero koli n > n 0 imamo T(n) = 2p A + str 2 T(n) ima vrstni red i 4 .

funkcija T(n) je povezan z določenim algoritmom, zato se pogosto reče, da je vrstni red kompleksnosti 0(/(n)) ima algoritem.

To pravijo T(p) Ima spodnja meja Q(g(n))(beri "omega big off g iz /r"), če obstaja konstanta c in količina podatkov n 0 tako da /P in obstaja neenakost T(n) > cg(n).

To dejstvo je zapisano kot T(n) = Q(g(n)). Naj npr. T(n) = 2. 4+ n 2 . Izbira vrednosti c = 1, za katero koli p imamo T(p)= 2. 4 + n 2 > cn A > Posledično T(n) ima spodnjo mejo i 4 .

Preprosto je videti, da vrstni red in spodnja meja za neko funkcijo nista edinstvena T(n). V zgornjih primerih lahko izberete /(i) kot i 5 , i 6 ,... in kot g(n) - i 3 , i 2 ,.... Običajno je funkcija z minimalno stopnjo izbrana kot /(i) in g(n)- z maksimumom.

Vrstni red kompleksnosti 0(/(i)) in spodnja meja Q(g(rc)) sta funkcijska razreda. Intuitivno lahko Q(g"(n)) razumemo kot razred funkcij, ki rastejo vsaj tako hitro kot T(n). Prav tako intuitivno 0(f(n)) lahko razumemo kot razred funkcij, ki rastejo ne hitreje kot T(n). OD S praktičnega vidika je pri ocenjevanju kompleksnosti algoritma najpomembnejši ravno razred funkcij. 0(f(n)). Določanje vrste funkcije /(i) in je glavna naloga računanja teoretična kompleksnost algoritma.

Za kateri koli algoritem lahko pri določanju stopnje rasti uporabite naslednje lastnosti 0(/(n)):

1) 0(kf(ji))= 0(/(i)), kjer je k= konst. Tako konstantni faktor v funkciji ne vpliva na stopnjo rasti. na primer

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Tako je vrstni red produkta dveh funkcij enak produktu njune kompleksnosti. na primer

Včasih je ta lastnost zapisana kot

3) 0(/(p) + g(n)) enako dominanten(funkcije z največjo stopnjo) funkcij f(n) in g(n). na primer

V teoriji kompleksnosti algoritmov ločimo naslednje razrede funkcij kompleksnosti:

1) konstantna kompleksnost 0(1). Čas delovanja algoritma in uporabljeni viri niso odvisni od količine vhodnih podatkov. Običajno so algoritmi, ki ne vsebujejo ciklov in rekurzivnih klicev, tako zapleteni;
2) linearna kompleksnost 0(n). Običajno so problemi te kompleksnosti tisti, pri katerih je treba vsak element vhodnih podatkov obdelati določeno število krat, ki ni v nobeni povezavi s številom obdelav drugih elementov;
3) logaritemska kompleksnost 0(log 2 w), 0(nog 2 n). Včasih se uporabljajo tudi druge osnove logaritma;
4) polinomska kompleksnost 0(i 2), 0(i 3), 0(i 4),...;
5) eksponentna kompleksnost 2 p, 3",....

Ko se velikost vnosa poveča, kompleksnost vsakega naslednjega tipa funkcije raste hitreje kot prejšnjega (razen 0(log 2 /?)). Za dovolj veliko količino vhodnih podatkov je bolje uporabiti manj zahtevne algoritme.

Pri kvantitativnem izračunu zahtevnosti se na začetku izbere operacija ali skupina operacij, ki je pomembna za ta algoritem (je njegova osnova). Običajno gre za primerjalne in aritmetične operacije. Primerjalne operacije vključujejo preverjanje vrednosti dveh količin (manj kot, več kot, enako, manj kot ali enako, večje ali enako, ni enako). Štejejo se za enakovredne glede na čas izvedbe. Aritmetične operacije pa so razdeljene na aditiv in multiplikativen. Na prvo (pogosto imenovano preprosto dodatek) vključujejo dodajanje, odštevanje, dekrementiranje ali dekrementiranje vrednosti števca. Na drugo (preprosto imenovano množenje) vključujejo množenje, deljenje, jemanje ostanka po modulu.

Seštevanja so hitrejša od množenja, zato imajo prednost algoritmi z manj množenji, tudi če število seštevanj raste sorazmerno s količino zmanjšanja množenja.

Operacije celoštevilskega množenja ali deljenja na potenco 2 uvrščamo med aditivne operacije, saj se pri delu s pomnilniškimi celicami reducirajo na premik, kar je enakovredno operaciji seštevanja.

Po izbiri pomembnih transakcij so razdeljene v dve kategoriji:

1) operacije, ki neposredno vplivajo na kompleksnost algoritma;
2) operacije, ki predstavljajo "režijske stroške" pri izvajanju algoritma (na primer dodeljevanje pomnilnika za shranjevanje vmesnih podatkov).

Neposredni izračun ali ocena števila izvedenih operacij vam omogoča oceno T(n).

Za oceno vrstnega reda kompleksnosti lahko uporabite analizo programske kode, ki implementira algoritem. pri čemer:

algoritmi brez zank in rekurzivnih klicev imajo kompleksnost reda 0(1). Tako imajo operacije dodeljevanja, vnosa in izpisa podatkov, pogojne konstrukcije stalno kompleksnost;
če sta dva dela programske kode zapletena 0(J ( (ri)) in 0(J 2 (n)), potem je zaporedna izvedba zapletena

če se telo zanke izvede enkrat za vsak element vhodnih podatkov, potem je kompleksnost izvajanja zanke reda 0(n)0( 1) = 0(n);
vrstni red zahtevnosti izvajanja ugnezdenih zank izračunamo s pravilom produkta 0(J x (n)f 2 (n)) = 0(/,(/?))- 0(J 2 (ri)).Če ima vsak od njih zahtevnost naročila 0(n), izvajanje ugnezdenih zank je zahtevno 0(n 2).

Primer 1.3

Določite vrstni red kompleksnosti programskega algoritma v jeziku

Pascal prikazan na seznamu 1.2. Programske vrstice so oštevilčene kot komentarji (glejte razdelek 2.6).

Seznam 1.2

(01) za i:=l do n do

(02) začeti

(03) write("Vnesite element polja

z indeksom ",i,": ");

(04) Readln(MyArray[i]);

(05) konec;

(06) za i:=l do n do

(07) za j:=1 do n do

(08) začeti

(09) write("Vnesite element polja

z indeksi ", i, ",", j, " : ");

(10) Readln(MyDArray);

(11) konec;

rešitev

Vrstice 02, 05, 08, 11 ne vsebujejo izvedljivih stavkov, zato se ne upoštevajo pri določanju naročila.

Vrstici 03 in 04 imata vrstni red 0(1). Njihovo zaporedno izvajanje ima vrstni red 0(1) + 0(1) = 0(1). Podobno ima zaporedna izvedba vrstic 09 in 10 kompleksnost 0(1).

Zanka v vrsticah 01-05 ima zapletenost reda O(n), ugnezdene zanke v vrsticah 06-11 - vrstni red 0(n 2). Končna kompleksnost algoritma je velikega reda

Ocena kompleksnosti algoritma, tako časa kot virov, vam omogoča, da določite največji in povprečni čas izvajanja algoritma. To je izjemno pomembno pri obdelavi velikih količin informacij, zlasti pri nalogah razvrščanja in iskanja, o katerih govorimo spodaj.