Beräkningskomplexitet

Beräkningskomplexitet är ett begrepp inom datavetenskap och teorin om algoritmer , som betecknar en funktion av beroendet av mängden arbete som utförs av någon algoritm på storleken på indata. Den gren som studerar beräkningskomplexitet kallas beräkningskomplexitetsteori . Mängden arbete mäts vanligtvis i termer av abstrakta begrepp om tid och rum som kallas datorresurser . Tiden bestäms av antalet elementära steg som krävs för att lösa ett problem, medan utrymmet bestäms av mängden minne eller lagringsutrymme . På detta område försöker man alltså svara på den centrala frågan om algoritmutveckling: "hur kommer exekveringstiden och mängden upptaget minne att förändras beroende på storleken på ingången?". Här är storleken på inmatningen längden på beskrivningen av problemdata i bitar (till exempel i resandeförsäljarproblemet är längden på inmatningen nästan proportionell mot antalet städer och vägar mellan dem), och storleken på produktionen är längden på beskrivningen av lösningen på problemet (den bästa vägen i resandeförsäljarproblemet).

I synnerhet definierar beräkningskomplexitetsteori NP-kompletta problem som en icke-deterministisk Turing-maskin kan lösa i polynomtid , medan ingen polynomalgoritm är känd för en deterministisk Turing-maskin . Vanligtvis är dessa komplexa optimeringsproblem , till exempel problemet med resande säljare .

Nära besläktade med teoretisk datavetenskap är områden som analys av algoritmer och teorin om beräkningsbarhet . Kopplingen mellan teoretisk datavetenskap och algoritmisk analys är det faktum att deras bildande ägnas åt analys av den erforderliga mängden resurser för vissa algoritmer för att lösa problem, medan en mer allmän fråga är möjligheten att använda algoritmer för sådana problem. För att vara specifik kommer vi att försöka klassificera problem som kan eller inte kan lösas med begränsade resurser. En stark begränsning av tillgängliga resurser skiljer beräkningskomplexitetsteori från beräkningsteori, den senare svarar på frågan om vilka problem som i princip kan lösas algoritmiskt.

Tid och rumskomplexitet

Teorin om beräkningskomplexitet uppstod ur behovet av att jämföra hastigheten på algoritmer, tydligt beskriva deras beteende (exekveringstid och mängd minne som krävs) beroende på storleken på ingången.

Antalet elementära operationer som används av algoritmen för att lösa en viss instans av problemet beror inte bara på storleken på indata, utan också på själva data. Till exempel är antalet operationer för insättningssorteringsalgoritmen mycket mindre om indata redan är sorterade . För att undvika sådana svårigheter, överväg begreppet tidskomplexitet för algoritmen i värsta fall .

Tidskomplexiteten för en algoritm (i värsta fall) är en funktion av storleken på indata, lika med det maximala antalet elementära operationer som utförs av algoritmen för att lösa en probleminstans av den specificerade storleken.

På samma sätt som begreppet tidskomplexitet i värsta fall definieras begreppet tidskomplexitet för en algoritm i bästa fall . De överväger också konceptet med den genomsnittliga körtiden för algoritmen , det vill säga den matematiska förväntningen på algoritmens körtid. Ibland sägs det helt enkelt: " Algoritmens tidskomplexitet " eller " Algoritmens körtid ", hänvisar till algoritmens tidskomplexitet i det sämsta, bästa eller genomsnittliga fallet (beroende på sammanhanget).

I analogi med tidskomplexitet bestämmer de algoritmens rumsliga komplexitet , bara här talar de inte om antalet elementära operationer, utan om mängden minne som används.

Asymptotisk komplexitet

Trots det faktum att tidskomplexitetsfunktionen för en algoritm kan bestämmas exakt i vissa fall, är det i de flesta fall meningslöst att leta efter dess exakta värde. Faktum är att för det första beror det exakta värdet på tidskomplexitet på definitionen av elementära operationer (exempelvis kan komplexitet mätas i antalet aritmetiska operationer, bitoperationer eller operationer på en Turing-maskin ), och för det andra, som storleken på indata ökar, bidraget av konstantfaktorer och termer av lägre ordning som förekommer i uttrycket för den exakta drifttiden blir extremt obetydligt.

Att beakta stora indata och uppskatta tillväxtordningen för algoritmens gångtid leder till konceptet med algoritmens asymptotiska komplexitet . Samtidigt är en algoritm med mindre asymptotisk komplexitet mer effektiv för all indata, utom, möjligen, för data av liten storlek. Den asymptotiska notationen används för att skriva den asymptotiska komplexiteten hos algoritmer :

Beteckning	Intuitiv förklaring	Definition
$f(n)\in O(g(n))$	$f$ begränsas ovanifrån av en funktion (upp till en konstant faktor) asymptotiskt $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ eller $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\i \Omega (g(n))$	$f$ begränsas underifrån av en funktion (upp till en konstant faktor) asymptotiskt $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\i \Theta (g(n))$	$f$ begränsas underifrån och ovan av funktionen asymptotiskt $g$	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|\leq \|C' g(n)\|$
$f(n)\in o(g(n))$	$g$ dominerar asymptotiskt $f$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\i \omega (g(n))$	$f$ dominerar asymptotiskt $g$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$f$ är ekvivalent asymptotiskt $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Exempel

Att ”dammsuga en matta” tar tid linjärt beroende på dess yta ( ), det vill säga en matta med dubbelt så stor yta tar dubbelt så lång tid. Följaktligen, med en ökning av mattans yta med hundra tusen gånger, ökar arbetsvolymen strikt proportionellt med hundra tusen gånger, etc. $\Theta (A)$
"Hitta ett namn i telefonboken" tar bara tid, logaritmiskt beroende på antalet poster ( ), för genom att öppna boken ungefär i mitten minskar vi storleken på det "återstående problemet" med hälften (genom att sortera namnen alfabetiskt). I en bok med en volym på 1000 sidor finns alltså inget namn mer än åt gången (boköppningar). När man ökar volymen av sidor till hundra tusen löses problemet fortfarande i besök. (Se binär sökning .) $O(\log _{2}(n))$ $\log _{2}1000\ca 10$ $\log _{2}100000\ca 17$

Anteckningar

Eftersom , i den asymptotiska komplexitetsuppskattningen, skrivs "logaritmen" ofta utan att nämna basen - till exempel . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Det bör betonas att tillväxttakten för den värsta exekveringstiden inte är det enda eller viktigaste kriteriet för att utvärdera algoritmer och program. Här är några överväganden som gör att du kan titta på körtidskriteriet ur andra synvinklar:

Om programmet som skapas endast kommer att användas ett fåtal gånger, kommer kostnaden för att skriva och felsöka programmet att dominera den totala kostnaden för programmet, det vill säga den faktiska exekveringstiden kommer inte att ha någon betydande inverkan på den totala kostnaden. I det här fallet bör den algoritm som är enklast att implementera föredras.

Om programmet bara kommer att fungera med "små" indata, så kommer tillväxthastigheten för körtiden att vara mindre viktig än den konstant som finns i körtidsformeln [1] . Samtidigt beror begreppet "liten" av indata också på den exakta exekveringstiden för konkurrerande algoritmer. Det finns algoritmer, som heltalsmultiplikationsalgoritmen , som asymptotiskt är de mest effektiva, men som aldrig används i praktiken, även för stora problem, eftersom deras proportionalitetskonstanter är mycket överlägsna andra, enklare och mindre "effektiva" algoritmer. Ett annat exempel är Fibonacci-högar , trots sin asymptotiska effektivitet, ur praktisk synvinkel, mjukvarukomplexiteten i implementeringen och stora värden på konstanter i formlerna för löptid gör dem mindre attraktiva än vanliga binära träd [1] .

Om lösningen av något problem för en n-vertexgraf med en algoritm tar tid (antal steg) av storleksordningen n C , och med en annan - av storleksordningen n+n!/C, där C är ett konstant tal , då enligt "polynomideologin" är den första algoritmen praktiskt taget effektiv , och den andra inte, även om till exempel vid C=10 (10 10 ) situationen är precis den motsatta [2] .A.A. Zykov

Det finns fall då effektiva algoritmer kräver så stora mängder maskinminne (utan möjlighet att använda externa lagringsmedia) att denna faktor omintetgör fördelen med algoritmens "effektivitet". Alltså är inte bara "tidskomplexitet" ofta viktig utan också "minneskomplexitet" (spatial komplexitet).

I numeriska algoritmer är algoritmernas noggrannhet och stabilitet inte mindre viktig än deras tidseffektivitet.

Svårighetsklasser

En komplexitetsklass är en uppsättning igenkänningsproblem för vilka det finns algoritmer som liknar beräkningskomplexiteten. Två viktiga representanter:

Klass P

Klassen P innehåller alla de problem vars lösning anses "snabb", det vill säga vars lösningstid beror polynomiellt på storleken på inmatningen. Detta inkluderar sortering , sökning i en array, ta reda på anslutningsmöjligheterna för grafer och många andra.

Klass NP

Klassen NP innehåller problem som en icke-deterministisk Turing-maskin kan lösa i ett polynomantal steg från storleken på inmatningen. Deras lösning kan kontrolleras av en deterministisk Turing-maskin i ett polynomantal steg. Det bör noteras att en icke-deterministisk Turing-maskin endast är en abstrakt modell, medan moderna datorer motsvarar en deterministisk Turing-maskin med begränsat minne. Eftersom en deterministisk Turing-maskin kan ses som ett specialfall av en icke -deterministisk Turing-maskin , inkluderar NP-klassen P-klassen såväl som några problem för vilka endast algoritmer som beror exponentiellt på indatastorlek (dvs. är ineffektiva för stora ingångar) är kända för att lösa. NP-klassen innehåller många kända problem, såsom resandeförsäljarproblemet , tillfredsställbarhetsproblemet för booleska formler , faktorisering , etc.

Problemet med jämlikheten mellan klasserna P och NP

Frågan om dessa två klassers jämlikhet anses vara ett av de svåraste öppna problemen inom teoretisk datavetenskap. Clay Mathematical Institute har inkluderat detta problem på sin lista över Millenniumproblem och erbjuder en belöning på en miljon US dollar för sin lösning.

Se även

Anteckningar

↑ 1 2 Cormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford. Algoritmer: Konstruktion och analys, 2:a upplagan = Introduktion till algoritmer andra upplagan. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. Grunderna i grafteorin. - 3:e uppl. - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 sid. — ISBN 5-9502-0057-8 .

Länkar

Girsh EA " Computational Complexity and Fundamentals of Cryptography " . En kurs med föreläsningar som beskriver grunderna i beräkningskomplexitet och kryptografi.
Yuri Lifshits " Modern problem of theoretical informatics " . Kurs med föreläsningar om algoritmer för NP-hårda problem.
A.A. Razborov . Teoretisk datavetenskap: en matematikers syn // Computerra . - 2001. - Nr 2 . (nedlänk)(alternativ länk)
A. A. RAZBOROV Om beräkningarnas komplexitet // Matematisk utbildning . - MTSNMO , 1999. - Nr 3 . - S. 127-141 .

Ordböcker och uppslagsverk	Stor ryss

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA