Laskennallinen monimutkaisuus

Laskennallinen monimutkaisuus on tietojenkäsittelytieteen ja algoritmien teorian käsite , joka kuvaa funktiota jonkin algoritmin suorittaman työn määrän riippuvuudesta syötetietojen koosta. Laskennallista monimutkaisuutta tutkivaa alaa kutsutaan laskennallisen monimutkaisuuden teoriaksi . Työn määrää mitataan yleensä abstrakteilla ajan ja tilan käsitteillä, joita kutsutaan laskentaresurssiksi . Aika määräytyy ongelman ratkaisemiseen tarvittavien perusvaiheiden lukumäärän mukaan, kun taas tila määräytyy tallennusvälineen muistin tai tilan määrän mukaan.. Tällä alueella yritetään siis vastata algoritmien kehittämisen keskeiseen kysymykseen: "miten suoritusaika ja varatun muistin määrä muuttuvat syötteen koosta riippuen?". Tässä syötteen koko on ongelmatietojen kuvauksen pituus bitteinä (esimerkiksi matkustava myyjä -tehtävässä syötteen pituus on lähes verrannollinen kaupunkien ja niiden välisten teiden lukumäärään), ja tulosteen koko on ongelman ratkaisun kuvauksen pituus (paras reitti matkustajamyyjäongelmassa).

Erityisesti laskennallinen monimutkaisuusteoria määrittelee NP-täydelliset ongelmat , jotka ei-deterministinen Turingin kone voi ratkaista polynomiajassa , kun taas deterministiselle Turingin koneelle ei tunneta polynomialgoritmia . Yleensä nämä ovat monimutkaisia optimointiongelmia , esimerkiksi matkamyyjän ongelma .

Tietojenkäsittelyteoriaan liittyvät läheisesti muun muassa algoritmien analysointi ja laskettavuusteoria . Teoreettisen tietojenkäsittelytieteen ja algoritmisen analyysin välinen yhteys on se, että niiden muodostus on omistettu tiettyjen ongelmien ratkaisemiseen tarvittavien algoritmien resurssien analysointiin, kun taas yleisempi kysymys on mahdollisuus käyttää algoritmeja tällaisiin ongelmiin. Tarkemmin sanottuna yritämme luokitella ongelmat, jotka voidaan ratkaista rajallisilla resursseilla tai joita ei voida ratkaista. Käytettävissä olevien resurssien voimakas rajoitus erottaa laskennallisen kompleksisuusteorian laskennallisesta teoriasta, joka vastaa kysymykseen, mitkä ongelmat periaatteessa voidaan ratkaista algoritmisesti.

Aika ja tila monimutkaisuus

Laskennallisen monimutkaisuuden teoria syntyi tarpeesta vertailla algoritmien nopeuksia, kuvata selkeästi niiden käyttäytymistä (suoritusaika ja tarvittava muistimäärä) syötteen koosta riippuen.

Algoritmin käyttämien perusoperaatioiden määrä tietyn ongelman ilmentymän ratkaisemiseen ei riipu pelkästään syötetietojen koosta, vaan myös itse tiedosta. Esimerkiksi lisäyslajittelualgoritmin operaatioiden määrä on paljon pienempi, jos syötetiedot on jo lajiteltu . Tällaisten vaikeuksien välttämiseksi harkitse algoritmin aikamonimutkaisuuden käsitettä pahimmassa tapauksessa .

Algoritmin aikamonimutkaisuus (pahimmassa tapauksessa) on syötetietojen koon funktio, joka on yhtä suuri kuin algoritmin suorittamien perustoimintojen enimmäismäärä määritellyn kokoisen ongelman ratkaisemiseksi.

Samoin kuin pahimmassa tapauksessa aikamonimutkaisuuden käsite , määritellään myös algoritmin aikamonimutkaisuuden käsite parhaassa tapauksessa . He ottavat myös huomioon algoritmin keskimääräisen käyntiajan käsitteen , eli algoritmin käyntiajan matemaattisen odotuksen . Joskus sanotaan yksinkertaisesti: " Algoritmin aikamonimutkaisuus " tai " Algoritmin ajoaika ", viitaten algoritmin aikaiseen monimutkaisuuteen pahimmassa, parhaassa tai keskimääräisessä tapauksessa (riippuen kontekstista).

Analogisesti aikamonimutkaisuuden kanssa ne määrittävät algoritmin spatiaalisen monimutkaisuuden , mutta tässä ei puhuta alkeisoperaatioiden lukumäärästä, vaan käytetyn muistin määrästä.

Asymptoottinen monimutkaisuus

Huolimatta siitä, että algoritmin aikamonimutkaisuusfunktio voidaan joissain tapauksissa määrittää tarkasti, on useimmiten turha etsiä sen tarkkaa arvoa. Tosiasia on, että ensinnäkin ajan monimutkaisuuden tarkka arvo riippuu alkeisoperaatioiden määrittelystä (monimutkaisuus voidaan mitata esimerkiksi aritmeettisten operaatioiden, bittioperaatioiden tai Turingin koneen operaatioiden lukumäärällä ), ja toiseksi, kuten syöttötiedon koko kasvaa, vakiotekijöiden ja alemman kertaluvun termien osuus tarkan toiminta-ajan lausekkeessa tulee erittäin merkityksettömäksi.

Suuren syöttödatan huomioon ottaminen ja algoritmin käyntiajan kasvujärjestyksen arvioiminen johtaa käsitykseen algoritmin asymptoottisesta kompleksisuudesta . Samalla algoritmi, jolla on vähemmän asymptoottista monimutkaisuutta, on tehokkaampi kaikille syöttötiedoille, paitsi mahdollisesti pienikokoisille tiedoille. Asymptoottista merkintää käytetään algoritmien asymptoottisen monimutkaisuuden kirjoittamiseen :

Nimitys	Intuitiivinen selitys	Määritelmä
$f(n)\in O(g(n))$	$f$ ylhäältä rajoittuu funktiolla (vakiotekijään asti) asymptoottisesti $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq \|Cg(n)\|$ tai $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\in \Omega (g(n))$	$f$ on alhaalta rajattu funktiolla (vakiotekijään asti) asymptoottisesti $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|Cg(n)\|\leq \|f(n)\|$
$f(n)\in \Theta (g(n))$	$f$ funktion rajoittama alhaalta ja ylhäältä asymptoottisesti $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$ hallitsee asymptoottisesti $f$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|f(n)\|<\|Cg(n)\|$
$f(n)\in \omega (g(n))$	$f$ hallitsee asymptoottisesti $g$	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;\|Cg(n)\|<\|f(n)\|$
$f(n)\sim g(n)$	$f$ vastaa asymptoottisesti $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Esimerkkejä

"maton imurointi" vie aikaa lineaarisesti sen pinta-alasta riippuen ( ), eli kaksinkertainen matto kestää kaksi kertaa kauemmin. Näin ollen, kun maton pinta-ala kasvaa satatuhatta kertaa, työn määrä kasvaa tiukasti suhteellisesti satatuhatta kertaa jne. $\Theta (A)$
"Etsi nimi puhelinluettelosta" vie vain aikaa, logaritmisesti merkintöjen määrästä ( ) riippuen , koska avaamalla kirjan suunnilleen keskeltä pienennämme "jäljellä olevan ongelman" kokoa puoleen (lajittelemalla nimet aakkosjärjestyksessä). Siten 1000-sivuisessa kirjassa mitä tahansa nimeä löytyy vain kerrallaan (kirjan avaukset). Kun sivumäärä nostetaan sataantuhanteen, ongelma ratkeaa silti käynneillä. (Katso binäärihaku .) $O(\log _{2}(n))$ $\log _{2}1000\noin 10$ $\log _{2}100000\noin 17$

Muistiinpanot

Koska asymptoottisessa monimutkaisuusestimaatissa "logaritmi" kirjoitetaan usein ilman kantaa - esimerkiksi . $\log _{a}b={\frac {\log _{c}b}{\log _{c}a))$ $O(n\log n)$

On syytä korostaa, että pahimman tapauksen suoritusajan kasvunopeus ei ole ainoa tai tärkein kriteeri algoritmien ja ohjelmien arvioinnissa. Tässä on muutamia huomioita, joiden avulla voit tarkastella suoritusaikakriteeriä muista näkökulmista:

Jos luotavaa ohjelmaa käytetään vain muutaman kerran, niin ohjelman kirjoittamisen ja virheenkorjauksen kustannukset hallitsevat ohjelman kokonaiskustannuksia, eli todellisella suoritusajalla ei ole merkittävää vaikutusta kokonaiskustannuksiin. Tässä tapauksessa tulee valita yksinkertaisin toteuttaa algoritmi.

Jos ohjelma toimii vain "pienillä" syötetiedoilla, ajoajan kasvunopeus on vähemmän tärkeä kuin ajoaikakaavassa oleva vakio [1] . Samaan aikaan syöttötietojen ”pienyyden” käsite riippuu myös kilpailevien algoritmien tarkasta suoritusajasta. On olemassa algoritmeja, kuten kokonaislukujen kertolaskualgoritmi , jotka ovat asymptoottisesti tehokkaimpia, mutta joita ei koskaan käytetä käytännössä edes suuriin ongelmiin, koska niiden suhteellisuusvakiot ovat huomattavasti parempia kuin muiden, yksinkertaisempien ja vähemmän "tehokkaiden" algoritmeja. Toinen esimerkki on Fibonacci-kasat , huolimatta niiden asymptoottisesta tehokkuudesta, käytännön näkökulmasta, ohjelmiston toteutuksen monimutkaisuus ja suuret vakioarvot ajoaikakaavoissa tekevät niistä vähemmän houkuttelevia kuin tavalliset binääripuut [1] .

Jos jonkin tehtävän ratkaisu n-pisteen graafille yhdellä algoritmilla vie aikaa (askelmäärä) luokkaa n C ja toisella - luokkaa n+n!/C, missä C on vakioluku , silloin "polynomiideologian" mukaan ensimmäinen algoritmi on käytännössä tehokas ja toinen ei, vaikka esimerkiksi C=10:ssä (10 10 ) tilanne on juuri päinvastainen [2] .A. A. Zykov

On tapauksia, joissa tehokkaat algoritmit vaativat niin suuria määriä koneen muistia (ilman mahdollisuutta käyttää ulkoisia tallennusvälineitä), että tämä tekijä mitätöi algoritmin "tehokkuuden" edun. Näin ollen ei vain "ajan monimutkaisuus" ole usein tärkeä, vaan myös "muistin monimutkaisuus" (tila monimutkaisuus).

Numeerisissa algoritmeissa algoritmien tarkkuus ja vakaus ovat yhtä tärkeitä kuin niiden aikatehokkuus.

Vaikeusluokat

Monimutkaisuusluokka on joukko tunnistusongelmia , joille on olemassa algoritmeja, jotka ovat samanlaisia laskennallisen monimutkaisuuden suhteen. Kaksi tärkeää edustajaa:

Luokka P

Luokka P sisältää kaikki ne tehtävät, joiden ratkaisua pidetään "nopeana" eli joiden ratkaisuaika riippuu polynomiaalisesti syötteen koosta. Tämä sisältää lajittelun , haun taulukosta, kaavioiden liitettävyyden selvittämisen ja monia muita.

Luokka NP

NP-luokka sisältää ongelmia, jotka epädeterministinen Turingin kone voi ratkaista polynomimääräisellä askelmäärällä syötteen koosta. Niiden ratkaisu voidaan tarkistaa deterministisellä Turingin koneella polynomimääräisellä askelmäärällä. On huomattava, että ei-deterministinen Turingin kone on vain abstrakti malli, kun taas nykyaikaiset tietokoneet vastaavat determinististä Turingin konetta , jolla on rajoitettu muisti. Koska determinististä Turingin konetta voidaan pitää ei- deterministisen Turingin koneen erikoistapauksena , NP-luokka sisältää P-luokan sekä joitakin ongelmia, joissa vain algoritmit, jotka riippuvat eksponentiaalisesti syötteen koosta (ts. ovat tehottomia suurille koneille). syötteet) tiedetään ratkaisevan. NP-luokka sisältää monia kuuluisia ongelmia, kuten matkustava myyjä -ongelma , Boolen kaavojen tyytyväisyysongelma , tekijöiden jakaminen jne.

Luokkien P ja NP tasa-arvoongelma

Kysymystä näiden kahden luokan tasa-arvoisuudesta pidetään yhtenä vaikeimmista avoimista ongelmista teoreettisen tietojenkäsittelytieteen alalla. Clay Mathematical Institute on sisällyttänyt tämän ongelman Millennium Problems -luetteloonsa ja tarjoaa miljoonan Yhdysvaltain dollarin palkkion sen ratkaisusta.

Katso myös

Muistiinpanot

↑ 1 2 Cormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford. Algoritmit: Rakentaminen ja analyysi, 2. painos = Johdanto algoritmeihin toinen painos. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
↑ A. A. Zykov. Graafiteorian perusteet. - 3. painos - M . : Vuzovskaya kniga, 2004. - S. 10. - 664 s. — ISBN 5-9502-0057-8 .

Linkit

Girsh EA " Computational Complexity and Fundamentals of Cryptography " . Laskennallisen monimutkaisuuden ja kryptografian perusteita kuvaava luentokurssi.
Juri Lifshits " Teoreettisen informatiikan nykyaikaiset ongelmat " . Luentokurssi NP-kovien ongelmien algoritmeista.
A. A. Razborov . Teoreettinen tietojenkäsittelytiede: matemaatikon näkemys // Computerra . - 2001. - Nro 2 . (downlink)(vaihtoehtoinen linkki)
A. A. RAZBOROV Laskelmien monimutkaisuudesta // Matemaattinen koulutus . - MTSNMO , 1999. - Nro 3 . - S. 127-141 .

Sanakirjat ja tietosanakirjat	Iso venäläinen

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI