EITC/IS/CCTF Osnove teorije računske složenosti

Budući da količina resursa potrebnih za pokretanje algoritma varira s veličinom ulaza, složenost se obično izražava kao funkcija f(n), gdje je n veličina ulaza, a f(n) ili složenost u najgorem slučaju ( maksimalnu količinu potrebnih resursa za sve ulaze veličine n) ili prosječnu složenost slučaja (prosjek količine resursa za sve ulaze veličine n). Broj potrebnih elementarnih operacija na ulazu veličine n obično se navodi kao vremenska složenost, gdje se vjeruje da elementarne operacije traju konstantno vrijeme na određenom računaru i mijenjaju se samo za konstantan faktor kada se izvode na drugoj mašini. Količina memorije koju algoritam zahtijeva na ulazu veličine n poznata je kao kompleksnost prostora.

Vrijeme je resurs koji se najčešće smatra. Kada se izraz „složenost“ koristi bez kvalifikatora, obično se odnosi na složenost vremena.

Tradicionalne jedinice vremena (sekunde, minute i tako dalje) se ne koriste u teoriji složenosti jer se previše oslanjaju na izabrani kompjuter i napredak tehnologije. Na primjer, današnji kompjuter može izvršiti algoritam znatno brže od kompjutera iz 1960-ih, ali to je zbog tehnoloških otkrića u kompjuterskom hardveru, a ne zbog inherentnog kvaliteta algoritma. Cilj teorije složenosti je da kvantifikuje inherentne vremenske potrebe algoritama, ili fundamentalna vremenska ograničenja koja bi algoritam nametnuo bilo kom računaru. Ovo se postiže prebrojavanjem koliko se osnovnih operacija izvodi tokom izračunavanja. Ove procedure se obično nazivaju koracima jer se smatra da traju konstantno vrijeme na određenoj mašini (tj. na njih ne utiče količina inputa).

Drugi važan resurs je količina računarske memorije potrebne za izvođenje algoritama.

Drugi često korišteni resurs je količina aritmetičkih operacija. U ovom scenariju koristi se izraz „aritmetička složenost“. Vremenska složenost je općenito proizvod aritmetičke složenosti pomoću konstantnog faktora ako je poznato gornje ograničenje na veličinu binarne reprezentacije brojeva koji se javljaju tokom izračunavanja.

Veličina celih brojeva koji se koriste tokom izračunavanja nije ograničena za mnoge metode i nerealno je pretpostaviti da aritmetičke operacije zahtevaju fiksno vreme. Kao rezultat toga, vremenska složenost, također poznata kao složenost bita, može biti znatno veća od aritmetičke složenosti. Aritmetička poteškoća izračunavanja determinante nn cjelobrojne matrice, na primjer, je O(n^3) za standardne tehnike (Gausova eliminacija). Budući da se veličina koeficijenata može eksponencijalno proširiti tokom izračunavanja, složenost bita istih metoda je eksponencijalna u n. Ako se ove tehnike koriste zajedno sa multimodularnom aritmetikom, složenost bita se može smanjiti na O(n^4).

Složenost bita, u formalnom smislu, odnosi se na broj operacija nad bitovima potrebnih za pokretanje algoritma. Ona je jednaka vremenskoj složenosti do konstantnog faktora u većini računskih paradigmi. Broj operacija nad mašinskim riječima koje zahtijevaju računari proporcionalan je složenosti bita. Za realistične modele proračuna, vremenska složenost i složenost bita su stoga identični.

Resurs koji se često uzima u obzir pri sortiranju i pretraživanju je količina poređenja unosa. Ako su podaci dobro raspoređeni, to je dobar pokazatelj vremenske složenosti.

Na svim potencijalnim ulazima, brojanje koraka u algoritmu je nemoguće. Budući da složenost ulaza raste s njegovom veličinom, on se obično predstavlja kao funkcija veličine ulaza n (u bitovima), pa je složenost funkcija od n. Međutim, za ulaze iste veličine, složenost algoritma može značajno varirati. Kao rezultat toga, rutinski se koriste različite funkcije složenosti.

Složenost najgoreg slučaja je zbir sve složenosti za sve ulaze veličine n, dok je složenost prosječnog slučaja zbir cjelokupne složenosti za sve ulaze veličine n (ovo ima smisla, jer je broj mogućih ulaza date veličine konačan). Kada se termin „složenost“ koristi bez daljeg definisanja, uzima se u obzir najgori slučaj složenosti vremena.

Složenost najgoreg i prosječnog slučaja je notorno teško ispravno izračunati. Nadalje, ove tačne vrijednosti imaju malo praktične primjene jer bi svaka promjena paradigme stroja ili proračuna neznatno promijenila složenost. Nadalje, korištenje resursa nije važno za male vrijednosti n, stoga je lakoća implementacije često privlačnija od niske složenosti za male vrijednosti n.

Iz ovih razloga, najviše pažnje se posvećuje ponašanju kompleksnosti za veliko n, odnosno njenom asimptotičkom ponašanju kada se n približava beskonačnosti. Kao rezultat toga, velika O notacija se obično koristi za označavanje složenosti.

Računski modeli

Odabir računskog modela, koji se sastoji od specificiranja bitnih operacija koje se izvode u jedinici vremena, važan je u određivanju složenosti. Ovo se ponekad naziva Turing mašina sa više traka kada paradigma računanja nije posebno opisana.

Deterministički model proračuna je onaj u kojem su naredna stanja mašine i operacije koje treba izvršiti u potpunosti definisane prethodnim stanjem. Rekurzivne funkcije, lambda račun i Turingove mašine bili su prvi deterministički modeli. Mašine sa slučajnim pristupom (takođe poznate kao RAM mašine) su popularna paradigma za simulaciju računara u stvarnom svetu.

Kada računski model nije definiran, obično se pretpostavlja Turingova mašina s više traka. Na Tjuringovim mašinama sa više traka, vremenska složenost je ista kao i na RAM mašinama za većinu algoritama, iako je potrebna značajna pažnja u načinu na koji se podaci pohranjuju u memoriju da bi se postigla ova ekvivalentnost.

Mogu se napraviti različiti izbori u nekim koracima izračunavanja u nedeterminističkom modelu računarstva, kao što su nedeterminističke Turingove mašine. U teoriji složenosti, sve izvodljive opcije se razmatraju u isto vrijeme, a nedeterministička vremenska složenost je količina vremena koja je potrebna kada se uvijek donose najbolji izbori. Drugim riječima, izračunavanje se vrši istovremeno na onoliko (identičnih) procesora koliko je potrebno, a nedeterminističko vrijeme izračunavanja je vrijeme potrebno prvom procesoru da završi izračunavanje. Ovaj paralelizam se može koristiti u kvantnom računarstvu korištenjem superponiranih zapletenih stanja pri pokretanju specijalizovanih kvantnih algoritama, kao što je Shorova faktorizacija sitnih cijelih brojeva, na primjer.

Čak i ako takav računski model trenutno nije izvodljiv, on ima teorijski značaj, posebno u odnosu na P = NP problem, koji postavlja pitanje da li su klase složenosti proizvedene korištenjem "polinomskog vremena" i "nedeterminističkog polinomskog vremena" kao najmanje gornje razine. granice su iste. Na determinističkom računaru, simulacija NP-algoritma zahtijeva “eksponencijalno vrijeme”. Ako se zadatak može riješiti u polinomskom vremenu na nedeterminističkom sistemu, on pripada NP klasi težine. Ako je problem u NP i nije lakši od bilo kojeg drugog NP problema, kaže se da je NP-potpun. Problem ranca, problem trgovačkog putnika i problem Booleove zadovoljivosti su NP-potpuni kombinatorni problemi. Najpoznatiji algoritam ima eksponencijalnu složenost za sve ove probleme. Ako bi se bilo koji od ovih problema mogao riješiti u polinomskom vremenu na determinističkoj mašini, onda bi se svi NP problemi mogli riješiti i u polinomskom vremenu, i P = NP bi se uspostavio. Od 2017. godine, široko se pretpostavlja da je P NP, što implicira da je najgore situacije NP problema fundamentalno teško riješiti, tj. da im je potrebno mnogo duže od bilo kojeg izvodljivog vremenskog raspona (decenijama) s obzirom na zanimljive ulazne dužine.

Paralelno i distribuirano računarstvo

Paralelno i distribuirano računarstvo uključuje podelu obrade na više procesora koji svi rade u isto vreme. Osnovna razlika između različitih modela je način slanja podataka između procesora. Prijenos podataka između procesora je obično vrlo brz u paralelnom računarstvu, dok se prijenos podataka između procesora u distribuiranom računarstvu obavlja preko mreže i stoga je znatno sporiji.

Izračunavanje na N procesora uzima najmanje kvocijent za N vremena potrebnog jednom procesoru. U stvarnosti, budući da se neki podzadaci ne mogu paralelizirati i neki procesori će možda morati čekati rezultat od drugog procesora, ova teoretski idealna granica nikada neće biti postignuta.

Ključno pitanje složenosti je stoga razviti algoritme tako da proizvod vremena računanja na broj procesora bude što je moguće bliži vremenu potrebnom za izvođenje istog izračuna na jednom procesoru.

Kvantno računanje

Kvantni kompjuter je računar sa modelom izračunavanja zasnovanim na kvantnoj mehanici. Church-Turingova teza vrijedi za kvantne kompjutere, što implicira da bilo koji problem koji kvantni kompjuter može riješiti može biti riješen i Turingovom mašinom. Međutim, neki zadaci bi se teoretski mogli riješiti korištenjem kvantnog kompjutera umjesto klasičnog računara sa znatno nižom vremenskom složenošću. Za sada je to striktno teoretski, jer niko ne zna kako da razvije praktičan kvantni kompjuter.

Kvantna teorija složenosti stvorena je da istraži različite vrste problema koje mogu riješiti kvantni kompjuteri. Koristi se u post-kvantnoj kriptografiji, što je proces stvaranja kriptografskih protokola otpornih na kvantne kompjuterske napade.

Složenost problema (donje granice)

Najniži dio složenosti algoritama koji mogu riješiti problem, uključujući neotkrivene tehnike, je složenost problema. Kao rezultat toga, složenost problema je jednaka složenosti bilo kog algoritma koji ga rješava.

Kao rezultat, bilo koja složenost data u velikoj O notaciji predstavlja složenost i algoritma i pratećeg problema.

S druge strane, dobijanje netrivijalnih donjih granica složenosti problema je često teško, a postoji nekoliko strategija za to.

Da bi se riješila većina problema, svi ulazni podaci se moraju pročitati, za što je potrebno vrijeme proporcionalno veličini podataka. Kao rezultat, takvi problemi imaju barem linearnu složenost, ili, u velikoj omega notaciji, složenost Ω(n).

Neki problemi, poput onih iz kompjuterske algebre i računske algebarske geometrije, imaju vrlo velika rješenja. Budući da izlaz mora biti napisan, složenost je ograničena maksimalnom veličinom izlaza.

Broj poređenja potrebnih za algoritam sortiranja ima nelinearnu donju granicu Ω(nlogn). Kao rezultat toga, najbolji algoritmi za sortiranje su najefikasniji jer je njihova složenost O(nlogn). Činjenica da postoje n! načini organiziranja n stvari vodi do ove donje granice. Jer svako poređenje dijeli ovu kolekciju od n! redoslijeda na dva dijela, broj N poređenja potrebnih za razlikovanje svih redova mora biti 2N > n!, što implicira O(nlogn) prema Stirlingovoj formuli.

Svođenje problema na drugi problem je uobičajena strategija za postizanje ograničenja smanjene složenosti.

Razvoj algoritma

Procjena složenosti algoritma je važan element procesa dizajna jer pruža korisne informacije o performansama koje se mogu očekivati.

Čest je nesporazum da će, kao rezultat Murovog zakona, koji predviđa eksponencijalni rast moderne računarske snage, procena složenosti algoritama postati manje relevantna. Ovo je netačno jer povećana snaga omogućava obradu ogromnih količina podataka (big data). Na primjer, bilo koji algoritam bi trebao dobro funkcionirati za manje od sekunde kada sortira po abecednom redu listu od nekoliko stotina unosa, kao što je bibliografija knjige. S druge strane, za milion unosa (na primjer, telefonski brojevi velikog grada), osnovni algoritmi koji zahtijevaju O(n2) poređenja morali bi izvršiti trilion poređenja, što bi trajalo tri sata pri brzini od 10 milion poređenja u sekundi. Brzo sortiranje i sortiranje spajanjem, s druge strane, zahtijevaju samo nlogn poređenja (kao složenost prosječnog slučaja za prvo, kao složenost najgoreg slučaja za drugo). Ovo proizvodi oko 30,000,000 poređenja za n = 1,000,000, što bi trajalo samo 3 sekunde pri 10 miliona poređenja u sekundi.

Kao rezultat toga, procjena složenosti može omogućiti eliminaciju mnogih neefikasnih algoritama prije implementacije. Ovo se također može koristiti za fino podešavanje složenih algoritama bez potrebe za testiranjem svih mogućih varijanti. Proučavanje složenosti omogućava fokusiranje napora za povećanje efikasnosti implementacije određivanjem najskupljih koraka složenog algoritma.