Beregningsmæssig kompleksitet

Beregningsmæssig kompleksitet er et begreb inden for datalogi og teorien om algoritmer , der angiver en funktion af afhængigheden af mængden af arbejde, der udføres af en eller anden algoritme på størrelsen af inputdata. Den gren, der studerer beregningsmæssig kompleksitet, kaldes beregningskompleksitetsteori . Mængden af arbejde måles normalt i form af abstrakte begreber om tid og rum kaldet computerressourcer . Tid bestemmes af antallet af elementære trin, der kræves for at løse et problem, mens plads bestemmes af mængden af hukommelse eller lagerplads . På dette område forsøger man således at besvare det centrale spørgsmål om algoritmeudvikling: "hvordan vil eksekveringstiden og mængden af optaget hukommelse ændre sig afhængigt af størrelsen af inputtet?". Her er inputstørrelsen længden af beskrivelsen af problemdataene i bit (f.eks. i rejsende sælgerproblemet er længden af input næsten proportional med antallet af byer og veje mellem dem), og størrelsen af output er længden af beskrivelsen af løsningen på problemet (den bedste rute i det rejsende sælgerproblem).

Især definerer beregningsmæssig kompleksitetsteori NP-komplette problemer , som en ikke-deterministisk Turing-maskine kan løse i polynomiel tid , hvorimod ingen polynomiel algoritme er kendt for en deterministisk Turing-maskine . Normalt er disse komplekse optimeringsproblemer , for eksempel problemet med den rejsende sælger .

Nært beslægtet med teoretisk datalogi er områder som analyse af algoritmer og teorien om beregningsevne . Forbindelsen mellem teoretisk datalogi og algoritmisk analyse er det faktum, at deres dannelse er afsat til analyse af den nødvendige mængde ressourcer af visse algoritmer til at løse problemer, mens et mere generelt problem er muligheden for at bruge algoritmer til sådanne problemer. For at være specifikke, vil vi forsøge at klassificere problemer, der kan eller ikke kan løses med begrænsede ressourcer. En stærk begrænsning af tilgængelige ressourcer adskiller beregningskompleksitetsteori fra beregningsteori, sidstnævnte besvarer spørgsmålet om, hvilke problemer der i princippet kan løses algoritmisk.

Tid og rum kompleksitet

Teorien om beregningsmæssig kompleksitet opstod fra behovet for at sammenligne hastigheden af algoritmer, klart beskrive deres adfærd (udførelsestid og mængde af hukommelse påkrævet) afhængigt af størrelsen af input.

Antallet af elementære operationer brugt af algoritmen til at løse en bestemt instans af problemet afhænger ikke kun af størrelsen af inputdataene, men også af selve dataene. For eksempel er antallet af operationer af indsættelsessorteringsalgoritmen meget mindre, hvis inputdataene allerede er sorteret . For at undgå sådanne vanskeligheder skal du i værste fald overveje begrebet tidskompleksitet af algoritmen .

Tidskompleksiteten af en algoritme (i værste fald) er en funktion af størrelsen af inputdataene, svarende til det maksimale antal elementære operationer udført af algoritmen for at løse en probleminstans af den specificerede størrelse.

På samme måde som begrebet tidskompleksitet i værste fald er begrebet tidskompleksitet af en algoritme i bedste fald defineret . De overvejer også konceptet om den gennemsnitlige køretid for algoritmen , det vil sige den matematiske forventning om algoritmens køretid. Nogle gange siges det ganske enkelt: " Algoritmens tidskompleksitet " eller " Algoritmens køretid ", der henviser til algoritmens tidskompleksitet i det værste, bedste eller gennemsnitlige tilfælde (afhængigt af konteksten).

Analogt med tidskompleksitet bestemmer de den rumlige kompleksitet af algoritmen , kun her taler de ikke om antallet af elementære operationer, men om mængden af brugt hukommelse.

Asymptotisk kompleksitet

På trods af at tidskompleksitetsfunktionen af en algoritme kan bestemmes nøjagtigt i nogle tilfælde, er det i de fleste tilfælde meningsløst at lede efter dens nøjagtige værdi. Faktum er, at for det første afhænger den nøjagtige værdi af tidskompleksitet af definitionen af elementære operationer (for eksempel kan kompleksitet måles i antallet af aritmetiske operationer, bitoperationer eller operationer på en Turing-maskine ), og for det andet, som størrelsen af inputdataene øges, bidraget af konstantfaktorer og lavere ordens termer, der optræder i udtrykket for den nøjagtige driftstid, bliver ekstremt ubetydeligt.

At overveje store inputdata og estimere rækkefølgen af vækst af algoritmens køretid fører til konceptet om algoritmens asymptotiske kompleksitet . Samtidig er en algoritme med mindre asymptotisk kompleksitet mere effektiv for alle inputdata, undtagen muligvis for data af lille størrelse. Den asymptotiske notation bruges til at skrive den asymptotiske kompleksitet af algoritmer :

Betegnelse	Intuitiv forklaring	Definition
$f(n)\in O(g(n))$	$f$ er afgrænset ovenfra af en funktion (op til en konstant faktor) asymptotisk $g$	$\eksisterer (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ eller $\eksisterer (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\i \Omega (g(n))$	$f$ er afgrænset nedefra af en funktion (op til en konstant faktor) asymptotisk $g$	$\eksisterer (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\i \Theta (g(n))$	$f$ afgrænset nedefra og oven af funktionen asymptotisk $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$ dominerer asymptotisk $f$	$\forall (C>0),\eksisterer n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\i \omega (g(n))$	$f$ dominerer asymptotisk $g$	$\forall (C>0),\eksisterer n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$f$ er ækvivalent asymptotisk $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Eksempler

At "støvsuge et tæppe" tager tid lineært afhængigt af dets areal ( ), det vil sige, at et tæppe med dobbelt så stort areal vil tage dobbelt så lang tid. Følgelig, med en stigning i tæppets areal med hundrede tusinde gange, stiger arbejdsmængden strengt proportionalt med hundrede tusinde gange osv. $\Theta (A)$
"Find et navn i telefonbogen" tager kun tid, logaritmisk afhængig af antallet af poster ( ), for ved at åbne bogen cirka på midten, reducerer vi størrelsen af "resterende problem" til det halve (ved at sortere navnene alfabetisk). I en bog med et volumen på 1000 sider findes ethvert navn således ikke mere end ad gangen (bogåbninger). Når man øger mængden af sider til hundrede tusinde, løses problemet stadig i besøg. (Se binær søgning .) $O(\log _{2}(n))$ $\log _{2}1000\ca. 10$ $\log _{2}100000\ca. 17$

Noter

Da , i det asymptotiske kompleksitetsestimat er "logaritmen" ofte skrevet uden at nævne basen - for eksempel . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

Det skal understreges, at vækstraten for den værst tænkelige eksekveringstid ikke er det eneste eller det vigtigste kriterium for evaluering af algoritmer og programmer. Her er et par overvejelser, der giver dig mulighed for at se på runtime-kriteriet fra andre synspunkter:

Hvis programmet, der oprettes, kun vil blive brugt få gange, så vil omkostningerne ved at skrive og fejlfinde programmet dominere de samlede omkostninger for programmet, dvs. den faktiske eksekveringstid vil ikke have en væsentlig indflydelse på de samlede omkostninger. I dette tilfælde bør den algoritme, der er den enkleste at implementere, foretrækkes.

Hvis programmet kun vil arbejde med "små" inputdata, så vil væksthastigheden af køretiden være mindre vigtig end konstanten til stede i køretidsformlen [1] . Samtidig afhænger begrebet "småhed" af inputdata også af den nøjagtige eksekveringstid for konkurrerende algoritmer. Der er algoritmer, såsom heltalsmultiplikationsalgoritmen , der asymptotisk er de mest effektive, men som aldrig bliver brugt i praksis, selv til store problemer, fordi deres proportionalitetskonstanter er langt overlegne i forhold til andre, enklere og mindre "effektive" algoritmer. Et andet eksempel er Fibonacci-dynger , på trods af deres asymptotiske effektivitet, fra et praktisk synspunkt, gør softwarekompleksiteten af implementering og store værdier af konstanter i køretidsformlerne dem mindre attraktive end almindelige binære træer [1] .

Hvis løsningen af et problem for en n-vertex graf med én algoritme tager tid (antal trin) af størrelsesordenen n C , og med en anden - af størrelsesordenen n+n!/C, hvor C er et konstant tal , så er ifølge "polynomideologien" den første algoritme praktisk talt effektiv , og den anden er ikke, selvom situationen for eksempel ved C=10 (10 10 ) er lige modsat [2] .A. A. Zykov

Der er tilfælde, hvor effektive algoritmer kræver så store mængder maskinhukommelse (uden mulighed for at bruge eksterne lagermedier), at denne faktor ophæver fordelen ved "effektiviteten" af algoritmen. Således er ikke kun "tidskompleksitet" ofte vigtig, men også "hukommelseskompleksitet" (rumlig kompleksitet).

I numeriske algoritmer er nøjagtigheden og stabiliteten af algoritmer ikke mindre vigtig end deres tidseffektivitet.

Sværhedsklasser

En kompleksitetsklasse er et sæt genkendelsesproblemer, for hvilke der er algoritmer, der ligner hinanden i beregningsmæssig kompleksitet. To vigtige repræsentanter:

Klasse P

Klassen P indeholder alle de problemer, hvis løsning betragtes som "hurtig", det vil sige, hvis løsningstid afhænger polynomisk af størrelsen af inputtet. Dette omfatter sortering , søgning i et array, finde ud af forbindelsen mellem grafer og mange andre.

Klasse NP

NP-klassen indeholder problemer, som en ikke-deterministisk Turing-maskine kan løse i et polynomielt antal trin fra størrelsen af inputtet. Deres løsning kan kontrolleres af en deterministisk Turing-maskine i et polynomielt antal trin. Det skal bemærkes, at en ikke-deterministisk Turing-maskine kun er en abstrakt model, mens moderne computere svarer til en deterministisk Turing-maskine med begrænset hukommelse. Fordi en deterministisk Turing-maskine kan opfattes som et specialtilfælde af en ikke -deterministisk Turing-maskine , inkluderer NP-klassen P-klassen såvel som nogle problemer, for hvilke kun algoritmer, der afhænger eksponentielt af inputstørrelse (dvs. er ineffektive for store inputs) vides at løse. NP-klassen inkluderer mange berømte problemer, såsom rejsende sælgerproblemet , tilfredshedsproblemet for booleske formler , faktorisering osv.

Problemet med ligheden mellem klasserne P og NP

Spørgsmålet om ligheden mellem disse to klasser betragtes som et af de sværeste åbne problemer inden for teoretisk datalogi. Clay Mathematical Institute har inkluderet dette problem på sin liste over Millennium-problemer og tilbyder en belønning på en million amerikanske dollars for dets løsning.

Se også

Noter

↑ 1 2 Cormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford. Algoritmer: Konstruktion og analyse, 2. udgave = Introduktion til algoritmer anden udgave. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. Grundlæggende om grafteori. - 3. udg. - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 s. — ISBN 5-9502-0057-8 .

Links

Girsh EA " Computational Complexity and Fundamentals of Cryptography " . Et kursus med forelæsninger, der beskriver det grundlæggende i beregningsmæssig kompleksitet og kryptografi.
Yuri Lifshits " Moderne problemer med teoretisk informatik " . Forelæsningsforløb om algoritmer til NP-hårde problemer.
A. A. Razborov . Teoretisk datalogi: en matematikers opfattelse // Computerra . - 2001. - Nr. 2 . (downlink)(alternativt link)
A. A. RAZBOROV Om kompleksiteten af beregninger // Matematisk uddannelse . - MTSNMO , 1999. - Nr. 3 . - S. 127-141 .

Ordbøger og encyklopædier	Stor russer

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE