EITC/IS/CCTF Osnove teorije računalne 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čunalu i mijenjaju se samo za konstantan faktor kada se izvode na drugom stroju. Količina memorije koju algoritam zahtijeva na ulazu veličine n poznata je kao kompleksnost prostora.

Vrijeme se najčešće smatra resursom. Kada se izraz "složenost" koristi bez kvalifikatora, obično se odnosi na složenost vremena.

Tradicionalne jedinice vremena (sekunde, minute i tako dalje) ne koriste se u teoriji složenosti jer se previše oslanjaju na odabrano računalo i napredak tehnologije. Na primjer, današnje računalo može izvršiti algoritam znatno brže od računala iz 1960-ih, ali to je zbog tehnoloških otkrića u računalnom hardveru, a ne zbog inherentne kvalitete algoritma. Cilj teorije složenosti je kvantificirati inherentne vremenske potrebe algoritama ili temeljna vremenska ograničenja koja bi algoritam nametnuo svakom računalu. To se postiže prebrojavanjem koliko se osnovnih operacija izvodi tijekom računanja. Ovi se postupci obično nazivaju koracima jer se smatra da zahtijevaju konstantno vrijeme na određenom stroju (tj. na njih ne utječe količina ulaza).

Drugi važan resurs je količina računalne memorije potrebna 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 općenito je umnožak aritmetičke složenosti s konstantnim faktorom ako je poznato gornje ograničenje na veličinu binarnog prikaza brojeva koji se javljaju tijekom izračuna.

Veličina cijelih brojeva koji se koriste tijekom izračuna nije ograničena za mnoge metode i nerealno je pretpostaviti da aritmetičke operacije zahtijevaju fiksno vrijeme. 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 cjelobrojne matrice nn, na primjer, je O(n^3) za standardne tehnike (Gaussova eliminacija). Budući da bi se veličina koeficijenata mogla eksponencijalno proširiti tijekom izračunavanja, složenost bita istih metoda je eksponencijalna u n. Ako se ove tehnike koriste zajedno s multimodularnom aritmetikom, složenost bita se može smanjiti na O(n^4).

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

Resurs koji se često uzima u obzir pri sortiranju i pretraživanju je količina usporedbi 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 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 zbroj sve složenosti za sve ulaze veličine n, dok je složenost prosječnog slučaja zbroj sve složenosti za sve ulaze veličine n (ovo ima smisla, jer je broj mogućih ulaza dane veličine konačan). Kada se izraz "složenost" koristi bez daljnjeg definiranja, uzima se u obzir najgori slučaj složenosti vremena.

Složenost najgoreg i prosječnog slučaja notorno je teško ispravno izračunati. Nadalje, te točne vrijednosti imaju malu praktičnu primjenu jer bi svaka promjena u stroju ili paradigmi izračuna malo promijenila složenost. Nadalje, korištenje resursa nije važno za male vrijednosti n, stoga je jednostavnost implementacije često privlačnija od niske složenosti za male n.

Iz tih se razloga najviše pažnje posvećuje ponašanju složenosti za veliki n, odnosno 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čunalni modeli

Odabir modela računanja, koji se sastoji od specificiranja bitnih operacija koje se izvode u jedinici vremena, važan je za određivanje složenosti. Ovo se ponekad naziva Turingov stroj s više traka kada paradigma računanja nije posebno opisana.

Deterministički model računanja je onaj u kojem su naredna stanja stroja i operacije koje treba izvesti u potpunosti definirane prethodnim stanjem. Rekurzivne funkcije, lambda račun i Turingovi strojevi bili su prvi deterministički modeli. Strojevi s slučajnim pristupom (također poznati kao RAM-strojevi) popularna su paradigma za simulaciju računala u stvarnom svijetu.

Kada računski model nije definiran, obično se pretpostavlja Turingov stroj s više traka. Na Turingovim strojevima s više traka, vremenska složenost je ista kao i na RAM strojevima za većinu algoritama, iako je potrebna znatna pozornost u načinu na koji se podaci pohranjuju u memoriju da bi se postigla ova ekvivalentnost.

U nekim koracima izračunavanja u nedeterminističkom modelu računanja, kao što su nedeterministički Turingovi strojevi, mogu se napraviti različiti izbori. U teoriji složenosti, sve izvedive 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čun se obavlja istodobno na onoliko (identičnih) procesora koliko je potrebno, a nedeterminističko vrijeme izračunavanja je vrijeme potrebno prvom procesoru da dovrši izračun. Ovaj se paralelizam može koristiti u kvantnom računanju korištenjem superponiranih zapletenih stanja pri pokretanju specijaliziranih kvantnih algoritama, kao što je, na primjer, Shorova faktorizacija sitnih cijelih brojeva.

Čak i ako takav računski model trenutno nije izvediv, on ima teorijsko značenje, posebno u odnosu na P = NP problem, koji pita jesu li klase složenosti proizvedene korištenjem "polinomskog vremena" i "nedeterminističkog polinomskog vremena" kao najmanje gornje razine. granice su iste. Na determinističkom računalu, simulacija NP-algoritma zahtijeva “eksponencijalno vrijeme”. Ako se zadatak može riješiti u polinomskom vremenu na nedeterminističkom sustavu, 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 naprtnjače, problem trgovačkog putnika i problem Booleove zadovoljivosti svi 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čkom stroju, tada bi se svi NP problemi mogli riješiti i u polinomskom vremenu, a P = NP bi se ustanovilo. Od 2017. godine široko se pretpostavlja da je P NP, što implicira da je najgore situacije NP problema u osnovi teško riješiti, tj. da im je potrebno mnogo dulje od bilo kojeg izvedivog vremenskog raspona (desetljeća) s obzirom na zanimljive ulazne duljine.

Paralelno i distribuirano računalstvo

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

Izračun na N procesora traje najmanje kvocijent od N vremena potrebnog za jedan procesor. 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čni problem složenosti je stoga razviti algoritme tako da umnožak vremena računanja prema broju procesora bude što je moguće bliži vremenu potrebnom za izvođenje istog izračuna na jednom procesoru.

Kvantno računanje

Kvantno računalo je računalo s računskim modelom koji se temelji na kvantnoj mehanici. Church-Turingova teza vrijedi za kvantna računala, što implicira da se bilo koji problem koji kvantno računalo može riješiti može također riješiti Turingov stroj. Međutim, neki zadaci bi se teoretski mogli riješiti korištenjem kvantnog računala, a ne klasičnog računala sa znatno nižom vremenskom složenošću. Za sada je to strogo teoretski, jer nitko ne zna kako razviti praktično kvantno računalo.

Kvantna teorija složenosti stvorena je kako bi istražila različite vrste problema koje mogu riješiti kvantna računala. Koristi se u post-kvantnoj kriptografiji, što je proces stvaranja kriptografskih protokola koji su otporni na napade kvantnih računala.

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 jednaka je složenosti bilo kojeg algoritma koji ga rješava.

Kao rezultat toga, bilo koja složenost navedena u velikom O označavanju predstavlja složenost i algoritma i popratnog problema.

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

Kako bi se riješila većina problema, svi ulazni podaci moraju se 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 računalne 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 usporedbi potrebnih za algoritam sortiranja ima nelinearnu donju granicu Ω(nlogn). Kao rezultat toga, najbolji algoritmi za sortiranje su najučinkovitiji jer je njihova složenost O(nlogn). Činjenica da postoje n! načina organiziranja n stvari dovodi do ove donje granice. Jer svaka usporedba dijeli ovu zbirku od n! redoslijeda na dva dijela, broj N usporedbi potrebnih za razlikovanje svih redova mora biti 2N > n!, što implicira O(nlogn) prema Stirlingovoj formuli.

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

Razvoj algoritma

Procjena složenosti algoritma važan je element procesa projektiranja jer pruža korisne informacije o izvedbi koja se može očekivati.

Čest je nesporazum da će, kao rezultat Mooreova zakona, koji predviđa eksponencijalni rast moderne računalne snage, procjena složenosti algoritama postati manje relevantna. To je netočno jer povećana snaga omogućuje obradu golemih količina podataka (big data). Na primjer, bilo koji algoritam trebao bi dobro funkcionirati za manje od jedne sekunde kada abecedno sortira popis od nekoliko stotina unosa, kao što je bibliografija knjige. S druge strane, za milijun unosa (na primjer, telefonski brojevi velikog grada), osnovni algoritmi koji zahtijevaju O(n2) usporedbe morali bi izvršiti trilijun usporedbi, što bi trajalo tri sata pri brzini od 10 milijun usporedbi u sekundi. Brzo sortiranje i sortiranje spajanjem, s druge strane, zahtijevaju samo nlogn usporedbe (kao složenost prosječnog slučaja za prvo, kao složenost najgoreg slučaja za potonje). To proizvodi oko 30,000,000 usporedbi za n = 1,000,000, što bi trajalo samo 3 sekunde pri 10 milijuna usporedbi u sekundi.

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