EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrindai

Kadangi išteklių, reikalingų algoritmui vykdyti, kiekis skiriasi priklausomai nuo įvesties dydžio, sudėtingumas paprastai išreiškiamas kaip funkcija f(n), kur n yra įvesties dydis, o f(n) yra arba blogiausio atvejo sudėtingumas ( didžiausias išteklių kiekis, reikalingas visoms n dydžio įvestims) arba vidutinis atvejo sudėtingumas (išteklių kiekio vidurkis per visas n dydžio įvestis). Reikalingų elementarių operacijų skaičius su n dydžio įvestimi paprastai nurodomas kaip laiko sudėtingumas, kai manoma, kad elementariosios operacijos tam tikrame kompiuteryje užtrunka pastoviai laiko ir pasikeičia tik pastoviu veiksniu, kai jos vykdomos kitoje mašinoje. Atminties kiekis, kurio reikalauja algoritmas n dydžio įėjime, yra žinomas kaip erdvės sudėtingumas.

Laikas yra dažniausiai laikomas ištekliu. Kai terminas „sudėtingumas“ vartojamas be kvalifikacinės reikšmės, jis paprastai reiškia laiko sudėtingumą.

Tradiciniai laiko vienetai (sekundės, minutės ir tt) nenaudojami sudėtingumo teorijoje, nes jie pernelyg priklauso nuo pasirinkto kompiuterio ir technologijų pažangos. Pavyzdžiui, kompiuteris šiandien gali vykdyti algoritmą daug greičiau nei septintojo dešimtmečio kompiuteris, tačiau taip yra dėl technologinių laimėjimų kompiuterių aparatinėje įrangoje, o ne dėl būdingos algoritmo kokybės. Sudėtingumo teorijos tikslas yra kiekybiškai įvertinti algoritmams būdingus laiko poreikius arba pagrindinius laiko apribojimus, kuriuos algoritmas nustatytų bet kuriam kompiuteriui. Tai atliekama skaičiuojant, kiek pagrindinių operacijų atlikta skaičiavimo metu. Šios procedūros paprastai vadinamos etapais, nes manoma, kad tam tikroje mašinoje jos trunka pastoviai (ty joms įtakos neturi įvesties kiekis).

Kitas svarbus šaltinis yra kompiuterio atminties kiekis, reikalingas algoritmams atlikti.

Kitas dažnai naudojamas šaltinis yra aritmetinių operacijų kiekis. Šiame scenarijuje vartojamas terminas „aritmetinis sudėtingumas“. Laiko sudėtingumas paprastai yra aritmetinio sudėtingumo sandauga iš pastovaus koeficiento, jei yra žinomas viršutinis skaičiavimo metu atsirandančių skaičių dvejetainio atvaizdo dydžio apribojimas.

Skaičiuojant naudojamų sveikųjų skaičių dydis nėra ribojamas daugeliui metodų, todėl nerealu manyti, kad aritmetinėms operacijoms atlikti reikia fiksuoto laiko. Dėl to laiko sudėtingumas, taip pat žinomas kaip bitų sudėtingumas, gali būti žymiai didesnis nei aritmetinis sudėtingumas. Pavyzdžiui, nn sveikųjų skaičių matricos determinanto skaičiavimo aritmetinis sunkumas yra O(n^3) standartinėms technikoms (Gauso eliminacija). Kadangi skaičiavimo metu koeficientų dydis gali padidėti eksponentiškai, tų pačių metodų bitų sudėtingumas yra eksponentinis n. Jei šie metodai naudojami kartu su kelių modulių aritmetika, bitų sudėtingumą galima sumažinti iki O(n^4).

Bitų sudėtingumas formaliai reiškia operacijų su bitais, reikalingų algoritmui vykdyti, skaičių. Jis prilygsta laiko sudėtingumui iki pastovaus daugumos skaičiavimo paradigmų faktoriaus. Kompiuteriams reikalingų operacijų su mašininiais žodžiais skaičius yra proporcingas bitų sudėtingumui. Taigi realistiškiems skaičiavimo modeliams laiko sudėtingumas ir bitų sudėtingumas yra identiški.

Išteklius, į kurį dažnai atsižvelgiama rūšiuojant ir ieškant, yra įrašų palyginimų skaičius. Jei duomenys yra gerai išdėstyti, tai yra geras laiko sudėtingumo rodiklis.

Neįmanoma suskaičiuoti algoritmo žingsnių skaičiaus naudojant visas galimas įvestis. Kadangi įvesties sudėtingumas didėja didėjant jos dydžiui, jis paprastai vaizduojamas kaip įvesties dydžio n funkcija (bitais), todėl sudėtingumas yra n funkcija. Tačiau tokio paties dydžio įvesties algoritmo sudėtingumas gali labai skirtis. Dėl to įprastai naudojamos įvairios sudėtingumo funkcijos.

Blogiausio atvejo sudėtingumas yra visų n dydžio įvesties sudėtingumo suma, o vidutinis sudėtingumo atvejis yra visų n dydžio įėjimų sudėtingumo suma (tai prasminga, nes galimų tam tikro dydžio įvesčių skaičius yra baigtinis). Kai terminas „sudėtingumas“ vartojamas jo neapibrėžiant, atsižvelgiama į blogiausio atvejo laiko sudėtingumą.

Blogiausio ir vidutinio sudėtingumo atvejį sunku teisingai apskaičiuoti. Be to, šios tikslios reikšmės praktiškai nepritaikomos, nes bet koks mašinos ar skaičiavimo paradigmos pakeitimas šiek tiek pakeistų sudėtingumą. Be to, išteklių naudojimas nėra svarbus mažoms n reikšmėms, todėl įgyvendinimo paprastumas dažnai yra patrauklesnis nei mažas sudėtingumas mažoms n reikšmėms.

Dėl šių priežasčių didžiausias dėmesys skiriamas sudėtingumo elgesiui esant dideliam n, ty jo asimptotiniam elgesiui, kai n artėja prie begalybės. Dėl to sudėtingumui nurodyti dažniausiai naudojamas didelis O žymėjimas.

Skaičiavimo modeliai

Skaičiavimo modelio, kurį sudaro esminių per laiko vienetą atliekamų operacijų nurodymas, pasirinkimas yra svarbus nustatant sudėtingumą. Tai kartais vadinama daugiajuoste Tiuringo mašina, kai skaičiavimo paradigma nėra konkrečiai aprašyta.

Deterministinis skaičiavimo modelis yra toks, kuriame tolesnės mašinos būsenos ir atliekamos operacijos yra visiškai apibrėžtos ankstesnės būsenos. Rekursinės funkcijos, lambda skaičiavimas ir Tiuringo mašinos buvo pirmieji deterministiniai modeliai. Atsitiktinės prieigos mašinos (taip pat žinomos kaip RAM mašinos) yra populiari realaus pasaulio kompiuterių modeliavimo paradigma.

Kai skaičiavimo modelis neapibrėžtas, paprastai daroma prielaida, kad yra daugiajuostė Tiuringo mašina. Daugiajuostėse Turingo mašinose daugumos algoritmų laiko sudėtingumas yra toks pat kaip ir RAM įrenginiuose, nors norint pasiekti šį lygiavertiškumą, gali prireikti daug dėmesio duomenų saugojimui atmintyje.

Kai kuriuose nedeterministinio skaičiavimo modelio skaičiavimo etapuose, pavyzdžiui, nedeterministinėse Tiuringo mašinose, gali būti atliekami įvairūs pasirinkimai. Sudėtingumo teorijoje visi įmanomi variantai yra svarstomi tuo pačiu metu, o nedeterministinis laiko sudėtingumas yra laikas, kurio reikia, kai visada pasirenkami geriausi. Kitaip tariant, skaičiavimas atliekamas tuo pačiu metu tiek (identiškų) procesorių, kiek reikia, o nedeterministinio skaičiavimo laikas yra laikas, per kurį pirmasis procesorius užbaigia skaičiavimą. Šis lygiagretumas gali būti naudojamas kvantiniame skaičiavime, naudojant superpozicines susietas būsenas, kai vykdomi specializuoti kvantiniai algoritmai, pvz., Shor'o mažų sveikųjų skaičių faktorizacija.

Net jei toks skaičiavimo modelis šiuo metu nepraktiškas, jis turi teorinės reikšmės, ypač atsižvelgiant į P = NP problemą, kuri klausia, ar sudėtingumo klasės, gautos naudojant „polinominį laiką“ ir „nedeterministinį daugianario laiką“ yra mažiausiai viršutinės. ribos vienodos. Deterministiniame kompiuteryje NP algoritmo modeliavimas reikalauja „eksponentinio laiko“. Jei užduotį galima išspręsti daugianario laiku nedeterministinėje sistemoje, ji priklauso NP sudėtingumo klasei. Jei problema yra NP ir nėra lengvesnė už bet kurią kitą NP problemą, sakoma, kad ji yra visiškai NP. Kuprinės problema, keliaujančio pardavėjo problema ir Būlio patenkinimo problema yra NP užbaigtos kombinacinės problemos. Labiausiai žinomas algoritmas turi eksponentinį sudėtingumą visoms šioms problemoms spręsti. Jei kurį nors iš šių klausimų būtų galima išspręsti daugianario laiku deterministinėje mašinoje, tai visos NP problemos taip pat gali būti išspręstos polinominiu laiku ir būtų nustatytas P = NP. Nuo 2017 m. plačiai daroma prielaida, kad P NP, o tai reiškia, kad blogiausias NP problemų situacijas iš esmės sunku išspręsti, ty užtrunka daug ilgiau nei bet koks įmanomas laikotarpis (dešimtmečiai), atsižvelgiant į įdomius įvesties ilgius.

Lygiagretusis ir paskirstytasis skaičiavimas

Lygiagretusis ir paskirstytasis skaičiavimas apima apdorojimo padalijimą į kelis procesorius, kurie visi veikia tuo pačiu metu. Esminis skirtumas tarp įvairių modelių yra duomenų siuntimo tarp procesorių metodas. Duomenų perdavimas tarp procesorių paprastai yra labai greitas lygiagrečiame skaičiavime, o duomenų perdavimas tarp procesorių paskirstytoje kompiuterijoje vyksta tinkle, todėl yra daug lėtesnis.

Skaičiuojant N procesorių, reikia bent vieno procesoriaus laiko koeficiento N. Iš tikrųjų, kadangi kai kurių papildomų užduočių negalima lygiagretinti, o kai kuriems procesoriams gali tekti laukti rezultato iš kito procesoriaus, ši teoriškai ideali riba niekada nebus pasiekta.

Taigi pagrindinis sudėtingumo klausimas yra sukurti algoritmus, kad skaičiavimo laiko sandauga pagal procesorių skaičių būtų kuo artimesnė laikui, kurio reikia norint atlikti tą patį skaičiavimą viename procesoriuje.

Kvantinis skaičiavimas

Kvantinis kompiuteris yra kompiuteris su kvantine mechanika pagrįstu skaičiavimo modeliu. Church-Turing tezė galioja kvantiniams kompiuteriams, o tai reiškia, kad bet kokia problema, kurią gali išspręsti kvantinis kompiuteris, taip pat gali būti išspręsta Tiuringo mašina. Tačiau kai kurios užduotys teoriškai gali būti išspręstos naudojant kvantinį kompiuterį, o ne klasikinį kompiuterį, kurio laiko sudėtingumas yra žymiai mažesnis. Kol kas tai yra griežtai teorinė, nes niekas nežino, kaip sukurti praktinį kvantinį kompiuterį.

Kvantinio sudėtingumo teorija buvo sukurta siekiant ištirti įvairių tipų problemas, kurias gali išspręsti kvantiniai kompiuteriai. Jis naudojamas postkvantinėje kriptografijoje, kuri yra kriptografinių protokolų, atsparių kvantinio kompiuterio puolimui, kūrimo procesas.

Problemos sudėtingumas (apatinės ribos)

Algoritmų, galinčių išspręsti problemą, įskaitant neatrastus metodus, sudėtingumo trūkumas yra problemos sudėtingumas. Dėl to problemos sudėtingumas yra lygus bet kurio ją sprendžiančio algoritmo sudėtingumui.

Dėl to bet koks sudėtingumas, pateiktas dideliu O žymėjimu, reiškia ir algoritmo, ir lydinčios problemos sudėtingumą.

Kita vertus, gauti nereikšmingas žemesnes problemos sudėtingumo ribas dažnai yra sunku ir yra nedaug strategijų, kaip tai padaryti.

Norint išspręsti daugumą problemų, reikia nuskaityti visus įvesties duomenis, o tai užtrunka proporcingai duomenų dydžiui. Dėl to tokios problemos turi bent tiesinį sudėtingumą arba, kalbant apie didžiąją omega, sudėtingumą Ω (n).

Kai kurios problemos, tokios kaip kompiuterinės algebros ir skaičiavimo algebrinės geometrijos, turi labai didelių sprendimų. Kadangi išvestis turi būti parašyta, sudėtingumą riboja didžiausias išvesties dydis.

Rūšiavimo algoritmui reikalingas palyginimų skaičius turi netiesinę apatinę ribą Ω(nlogn). Dėl to geriausi rūšiavimo algoritmai yra efektyviausi, nes jų sudėtingumas yra O (nlogn). Tai, kad yra n! n dalykų organizavimo būdai veda prie šios apatinės ribos. Nes kiekvienas palyginimas padalija šią n rinkinį! užsakymus į dvi dalis, N palyginimų skaičius, reikalingas norint atskirti visas eiles, turi būti 2N > n!, o tai reiškia O(nlogn) pagal Stirlingo formulę.

Problemos sumažinimas kita problema yra įprasta strategija siekiant sumažinti sudėtingumo apribojimus.

Algoritmo kūrimas

Algoritmo sudėtingumo įvertinimas yra svarbus projektavimo proceso elementas, nes jis suteikia naudingos informacijos apie našumą, kurio galima tikėtis.

Dažnas nesusipratimas, kad dėl Moore'o dėsnio, numatančio eksponentinį šiuolaikinio kompiuterio galios augimą, algoritmų sudėtingumo vertinimas taps ne toks svarbus. Tai neteisinga, nes padidinta galia leidžia apdoroti didžiulius duomenų kiekius (didelius duomenis). Pavyzdžiui, bet koks algoritmas turėtų gerai veikti greičiau nei per sekundę, kai abėcėlės tvarka rūšiuojamas kelių šimtų įrašų sąrašas, pvz., knygos bibliografija. Kita vertus, milijonui įrašų (pavyzdžiui, didelio miesto telefono numerių) pagrindiniai algoritmai, kuriems reikia O(n2) palyginimų, turėtų atlikti trilijoną palyginimų, o tai užtruktų tris valandas 10 greičiu. milijonas palyginimų per sekundę. Kita vertus, greitojo rūšiavimo ir sujungimo rūšiavimui reikia tik nlogn palyginimų (kaip vidutinio sudėtingumo pirmiesiems atvejams, kaip blogiausio atvejo sudėtingumo antriesiems). Taip gaunama apie 30,000,000 1,000,000 3 palyginimų, kai n = 10 XNUMX XNUMX, o tai užtruktų tik XNUMX sekundes, kai palyginimai XNUMX milijonų per sekundę.

Dėl to sudėtingumo įvertinimas gali leisti pašalinti daugybę neveiksmingų algoritmų prieš įgyvendinant. Tai taip pat gali būti naudojama norint tiksliai suderinti sudėtingus algoritmus, nereikia išbandyti visų galimų variantų. Sudėtingumo tyrimas leidžia sutelkti pastangas didinti įgyvendinimo efektyvumą, nustatant brangiausius sudėtingo algoritmo žingsnius.