EITC/IS/CCTF Computational Complexity Theory Fundamentals

Omdat die hoeveelheid hulpbronne wat benodig word om 'n algoritme uit te voer, wissel met die grootte van die invoer, word die kompleksiteit gewoonlik uitgedruk as 'n funksie f(n), waar n die invoergrootte is en f(n) óf die ergste-geval kompleksiteit ( die maksimum hoeveelheid hulpbronne benodig oor alle insette van grootte n) of die gemiddelde-geval kompleksiteit (die gemiddelde van die hoeveelheid hulpbronne oor alle insette van grootte n). Die aantal vereiste elementêre bewerkings op 'n invoer van grootte n word algemeen aangegee as tydskompleksiteit, waar daar geglo word dat elementêre bewerkings 'n konstante hoeveelheid tyd op 'n spesifieke rekenaar neem en slegs deur 'n konstante faktor verander wanneer dit op 'n ander masjien uitgevoer word. Die hoeveelheid geheue wat deur 'n algoritme benodig word op 'n invoer van grootte n staan ​​bekend as ruimtekompleksiteit.

Tyd is die mees algemeen beskou as hulpbron. Wanneer die term "kompleksiteit" sonder kwalifiseerder gebruik word, verwys dit gewoonlik na die kompleksiteit van tyd.

Die tradisionele tydeenhede (sekondes, minute, ensovoorts) word nie in kompleksiteitsteorie aangewend nie, aangesien hulle te afhanklik is van die rekenaar wat gekies is en die vooruitgang van tegnologie. Byvoorbeeld, 'n rekenaar kan vandag 'n algoritme aansienlik vinniger uitvoer as 'n rekenaar uit die 1960's, maar dit is te danke aan tegnologiese deurbrake in rekenaarhardeware eerder as 'n inherente kwaliteit van die algoritme. Die doel van kompleksiteitsteorie is om die inherente tydsbehoeftes van algoritmes te kwantifiseer, of die fundamentele tydsbeperkings wat 'n algoritme op enige rekenaar sou oplê. Dit word bewerkstellig deur te tel hoeveel basiese bewerkings tydens die berekening uitgevoer word. Daar word gewoonlik na hierdie prosedures verwys as stappe omdat dit beskou word as konstante tyd op 'n spesifieke masjien (dws hulle word nie deur die hoeveelheid insette beïnvloed nie).

Nog 'n belangrike hulpbron is die hoeveelheid rekenaargeheue wat benodig word om algoritmes uit te voer.

Nog 'n hulpbron wat dikwels gebruik word, is die hoeveelheid rekenkundige bewerkings. In hierdie scenario word die term "rekenkundige kompleksiteit" gebruik. Die tydskompleksiteit is oor die algemeen die produk van die rekenkundige kompleksiteit deur 'n konstante faktor as 'n boonste beperking op die grootte van die binêre voorstelling van die getalle wat tydens 'n berekening voorkom, bekend is.

Die grootte van die heelgetalle wat tydens 'n berekening gebruik word, word nie vir baie metodes beperk nie, en dit is onrealisties om te aanvaar dat rekenkundige bewerkings 'n vaste hoeveelheid tyd benodig. Gevolglik kan die tydskompleksiteit, ook bekend as biskompleksiteit, aansienlik hoër wees as die rekenkundige kompleksiteit. Die rekenkundige moeilikheid om die determinant van 'n nn heelgetalmatriks te bereken, is byvoorbeeld O(n^3) vir standaardtegnieke (Gaussiese eliminasie). Omdat die grootte van die koëffisiënte eksponensieel kan uitbrei tydens die berekening, is die biskompleksiteit van dieselfde metodes eksponensieel in n. As hierdie tegnieke in samewerking met multi-modulêre rekenkunde gebruik word, kan die biskompleksiteit verminder word na O(n^4).

Die biskompleksiteit, in formele terme, verwys na die aantal bewerkings op bisse wat nodig is om 'n algoritme uit te voer. Dit is gelyk aan die tydelike kompleksiteit tot 'n konstante faktor in die meeste berekeningsparadigmas. Die aantal bewerkings op masjienwoorde wat deur rekenaars vereis word, is eweredig aan die biskompleksiteit. Vir realistiese modelle van berekening is die tydkompleksiteit en biskompleksiteit dus identies.

Die hulpbron wat dikwels oorweeg word by sortering en soek is die hoeveelheid inskrywingsvergelykings. As die data goed gerangskik is, is dit 'n goeie aanduiding van die tydskompleksiteit.

Op alle potensiële insette is dit onmoontlik om die aantal stappe in 'n algoritme te tel. Omdat die kompleksiteit van 'n inset toeneem met sy grootte, word dit algemeen voorgestel as 'n funksie van die inset se grootte n (in bisse), en dus is die kompleksiteit 'n funksie van n. Vir dieselfde-grootte insette kan die kompleksiteit van 'n algoritme egter aansienlik verskil. As gevolg hiervan word 'n verskeidenheid kompleksiteitsfunksies gereeld aangewend.

Die ergste-geval kompleksiteit is die som van alle kompleksiteit vir alle grootte n insette, terwyl die gemiddelde-geval kompleksiteit die som is van alle kompleksiteit vir alle grootte n insette (dit maak sin, aangesien die aantal moontlike insette van 'n gegewe grootte is eindig). Wanneer die term "kompleksiteit" gebruik word sonder om verder omskryf te word, word die ergste tydskompleksiteit in ag geneem.

Die ergste-geval en gemiddelde-geval kompleksiteit is berug moeilik om korrek te bereken. Verder het hierdie presiese waardes min praktiese toepassing omdat enige verandering in masjien of berekeningsparadigma die kompleksiteit effens sal verander. Verder is hulpbrongebruik nie belangrik vir klein waardes van n nie, daarom is die gemak van implementering dikwels meer aantreklik as lae kompleksiteit vir klein n.

Om hierdie redes word die meeste aandag gegee aan die kompleksiteit se gedrag vir hoë n, dit wil sê sy asimptotiese gedrag as n oneindigheid nader. As gevolg hiervan word groot O-notasie algemeen gebruik om kompleksiteit aan te dui.

Rekenkundige modelle

Die keuse van 'n berekeningsmodel, wat bestaan ​​uit die spesifikasie van die noodsaaklike bewerkings wat in 'n tydseenheid uitgevoer word, is belangrik om die kompleksiteit te bepaal. Dit word soms na verwys as 'n multitape Turing-masjien wanneer die berekeningsparadigma nie spesifiek beskryf word nie.

'n Deterministiese model van berekening is een waarin die masjien se daaropvolgende toestande en die bewerkings wat uitgevoer moet word, geheel en al deur die vorige toestand gedefinieer word. Rekursiewe funksies, lambda-rekening en Turing-masjiene was die eerste deterministiese modelle. Toevallige toegangsmasjiene (ook bekend as RAM-masjiene) is 'n gewilde paradigma om werklike rekenaars te simuleer.

Wanneer die berekeningsmodel nie gedefinieer is nie, word 'n multitape Turing-masjien gewoonlik aanvaar. Op multitape Turing-masjiene is die tydskompleksiteit dieselfde as op RAM-masjiene vir die meeste algoritmes, alhoewel aansienlike aandag in hoe data in die geheue gestoor word nodig mag wees om hierdie ekwivalensie te bereik.

Verskeie keuses kan gemaak word by sommige stappe van die berekening in 'n nie-deterministiese model van rekenaar, soos nie-deterministiese Turing-masjiene. In kompleksiteitsteorie word alle haalbare opsies gelyktydig oorweeg, en nie-deterministiese tydskompleksiteit is die hoeveelheid tyd wat benodig word wanneer die beste keuses altyd gemaak word. Om dit anders te stel, die berekening word gelyktydig gedoen op soveel (identiese) verwerkers as wat vereis word, en die nie-deterministiese berekeningstyd is die tyd wat die eerste verwerker neem om die berekening te voltooi. Hierdie parallellisme kan gebruik word in kwantumberekening deur gesuperponeerde verstrengelde toestande te gebruik wanneer gespesialiseerde kwantumalgoritmes uitgevoer word, soos byvoorbeeld Shor se faktorisering van klein heelgetalle.

Selfs al is so 'n berekeningsmodel nie tans prakties prakties nie, het dit teoretiese betekenis, veral met betrekking tot die P = NP-probleem, wat vra of die kompleksiteitsklasse geproduseer word deur die gebruik van "polinoomtyd" en "nie-deterministiese polinoomtyd" as die minste boonste grense is dieselfde. Op 'n deterministiese rekenaar vereis die simulering van 'n NP-algoritme "eksponensiële tyd." As 'n taak in polinoomtyd op 'n nie-deterministiese stelsel opgelos kan word, behoort dit tot die NP-moeilikheidsklas. As 'n kwessie in NP is en nie makliker is as enige ander NP-probleem nie, word gesê dat dit NP-volledig is. Die Rugsak-probleem, die reisende verkoopsman-probleem en die Boole-bevredigingsprobleem is almal NP-volledige kombinatoriese probleme. Die bekendste algoritme het eksponensiële kompleksiteit vir al hierdie probleme. As enige van hierdie kwessies in polinoomtyd op 'n deterministiese masjien opgelos kan word, dan kan alle NP-probleme ook in polinoomtyd opgelos word, en P = NP sal vasgestel word. Vanaf 2017 word dit algemeen aanvaar dat P NP, wat impliseer dat die ergste situasies van NP-probleme fundamenteel moeilik is om op te los, dit wil sê, neem baie langer as enige haalbare tydsbestek (dekades) gegewe interessante insetlengtes.

Parallelle en verspreide rekenaars

Parallelle en verspreide rekenaars behels die verdeling van verwerking oor verskeie verwerkers wat almal op dieselfde tyd werk. Die fundamentele onderskeid tussen die verskillende modelle is die metode om data tussen verwerkers te stuur. Data-oordrag tussen verwerkers is tipies baie vinnig in parallelle rekenaars, terwyl data-oordrag tussen verwerkers in verspreide rekenaars oor 'n netwerk gedoen word en dus aansienlik stadiger is.

'n Berekening op N verwerkers neem ten minste die kwosiënt met N van die tyd wat dit op 'n enkele verwerker neem. In werklikheid, omdat sommige subtake nie geparalleliseer kan word nie en sommige verwerkers dalk moet wag vir 'n resultaat van 'n ander verwerker, sal hierdie teoreties ideale binding nooit bereik word nie.

Die sleutelkompleksiteitskwessie is dus om algoritmes te ontwikkel sodat die produk van rekenaartyd deur die aantal verwerkers so na as moontlik aan die tyd is wat nodig is om dieselfde berekening op 'n enkele verwerker uit te voer.

Kwantumberekening

'n Kwantumrekenaar is 'n rekenaar met 'n kwantummeganika-gebaseerde berekeningsmodel. Die Church–Turing-proefskrif geld vir kwantumrekenaars, wat impliseer dat enige probleem wat 'n kwantumrekenaar kan oplos ook deur 'n Turing-masjien opgelos kan word. Sommige take kan egter teoreties opgelos word met 'n kwantumrekenaar eerder as 'n klassieke rekenaar met 'n aansienlik laer temporele kompleksiteit. Vir eers is dit streng teoreties, aangesien niemand weet hoe om 'n praktiese kwantumrekenaar te ontwikkel nie.

Kwantumkompleksiteitsteorie is geskep om die verskillende tipes kwessies wat deur kwantumrekenaars opgelos kan word, te ondersoek. Dit word gebruik in post-kwantumkriptografie, wat die proses is om kriptografiese protokolle te skep wat bestand is teen kwantumrekenaaraanvalle.

Kompleksiteit van die probleem (ondergrens)

Die infimum van die kompleksiteite van die algoritmes wat die probleem kan oplos, insluitend onontdekte tegnieke, is die kompleksiteit van die probleem. Gevolglik is die kompleksiteit van 'n probleem gelyk aan die kompleksiteit van enige algoritme wat dit oplos.

As gevolg hiervan verteenwoordig enige kompleksiteit wat in groot O-notasie gegee word 'n kompleksiteit van beide die algoritme en die gepaardgaande probleem.

Aan die ander kant is dit dikwels moeilik om nie-triviale ondergrense vir kwessiekompleksiteit te verkry, en daar is min strategieë om dit te doen.

Om die meeste probleme op te los, moet alle invoerdata gelees word, wat tyd neem in verhouding tot die omvang van die data. As gevolg hiervan het sulke probleme ten minste lineêre kompleksiteit, of, in groot omega-notasie, 'n kompleksiteit van Ω(n).

Sommige probleme, soos dié in rekenaaralgebra en berekeningsalgebraïese meetkunde, het baie groot oplossings. Omdat die uitvoer geskryf moet word, word die kompleksiteit beperk deur die maksimum grootte van die uitvoer.

Die aantal vergelykings wat benodig word vir 'n sorteeralgoritme het 'n nie-lineêre ondergrens van Ω(nlogn). As gevolg hiervan is die beste sorteeralgoritmes die doeltreffendste aangesien hul kompleksiteit O(nlogn) is. Die feit dat daar n! maniere om n dinge te organiseer lei tot hierdie ondergrens. Omdat elke vergelyking hierdie versameling van n verdeel! bestellings in twee stukke, moet die aantal N vergelykings wat nodig is om alle bestellings te onderskei 2N > n! wees, wat O(nlogn) deur Stirling se formule impliseer.

Om 'n probleem na 'n ander probleem te reduseer, is 'n algemene strategie vir die verkryging van verminderde kompleksiteitsbeperkings.

Algoritme ontwikkeling

Die evaluering van 'n algoritme se kompleksiteit is 'n belangrike element van die ontwerpproses aangesien dit nuttige inligting verskaf oor die prestasie wat verwag kan word.

Dit is 'n gereelde misverstand dat, as gevolg van Moore se wet, wat die eksponensiële groei van moderne rekenaarkrag voorspel, die evaluering van die kompleksiteit van algoritmes minder relevant sal word. Dit is verkeerd omdat die verhoogde krag voorsiening maak vir die verwerking van massiewe hoeveelhede data (groot data). Byvoorbeeld, enige algoritme behoort binne minder as 'n sekonde goed te funksioneer wanneer 'n lys van 'n paar honderde inskrywings, soos die bibliografie van 'n boek, alfabeties gesorteer word. Aan die ander kant, vir 'n miljoen inskrywings (byvoorbeeld die telefoonnommers van 'n groot stad), sal die basiese algoritmes wat O(n2)-vergelykings vereis 'n triljoen vergelykings moet uitvoer, wat drie uur teen 'n spoed van 10 sal neem miljoen vergelykings per sekonde. Quicksort en merge sort, aan die ander kant, vereis slegs nlogn-vergelykings (as gemiddelde-geval-kompleksiteit vir eersgenoemde, as ergste-geval-kompleksiteit vir laasgenoemde). Dit lewer ongeveer 30,000,000 1,000,000 3 vergelykings vir n = 10 XNUMX XNUMX, wat slegs XNUMX sekondes sal neem teen XNUMX miljoen vergelykings per sekonde.

As gevolg hiervan kan die beoordeling van kompleksiteit die uitskakeling van baie ondoeltreffende algoritmes voor implementering moontlik maak. Dit kan ook gebruik word om komplekse algoritmes te verfyn sonder om alle moontlike variante te toets. Die studie van kompleksiteit laat toe om die poging om die doeltreffendheid van 'n implementering te verhoog te fokus deur die duurste stappe van 'n komplekse algoritme te bepaal.