Laskennallinen kompleksisuusteoria
Laskennallinen kompleksisuusteoria on osa tietojenkäsittelytieteen alaa. Siinä tarkastellaan algoritmeja ja yritetään sanoa, kuinka monta askelta tai kuinka paljon muistia tietty algoritmi vaatii tietokoneelta. Hyvin usein algoritmit, jotka käyttävät vähemmän vaiheita, käyttävät enemmän muistia (tai päinvastoin: jos muistia on vähemmän, algoritmin tekemiseen tarvitaan enemmän vaiheita). Monet mielenkiintoiset algoritmit käyttävät askeleiden määrän, joka riippuu ongelman koosta.
Eri monimutkaisuusluokat
Jatkuva monimutkaisuus
Monimutkaisuusteoriassa tarkastellaan myös sitä, miten ongelma muuttuu, jos se tehdään useammalle elementille. Vakion kompleksisuusluokan ongelma on ainoa luokka, jossa tämä ei päde. Vakiokompleksinen ongelma vaatii saman määrän vaiheita riippumatta syötteen koosta tai elementtien lukumäärästä, jolle se lasketaan. Viestin lähettäminen voidaan ajatella vakiokompleksisuusluokan ongelmaksi. Riippumatta siitä, kuinka monen ihmisen on saatava viesti, kaikki voivat kuunnella yhtä lähetystä ilman ylimääräisiä lähetyksiä.
Lineaarinen monimutkaisuus
Nurmikonleikkuuta voidaan pitää lineaarisesti monimutkaisena ongelmana. Alkuperäistä kaksi kertaa suuremman alueen leikkuu kestää kaksi kertaa kauemmin.
Kvadraattinen monimutkaisuus
Oletetaan, että haluat tietää, ketkä ystävistäsi tuntevat toisensa. Sinun on kysyttävä jokaiselta ystäväparilta, tuntevatko he toisensa. Jos sinulla on kaksi kertaa enemmän ystäviä kuin jollakin toisella, sinun on kysyttävä neljä kertaa enemmän kysymyksiä saadaksesi selville, kenet kukin tuntee. Ongelmien, jotka kestävät neljä kertaa kauemmin, kun ongelman koko kaksinkertaistuu, sanotaan olevan nelinkertaisen monimutkaisia.
Logaritminen monimutkaisuus
Tämä on usein monimutkaista ongelmissa, jotka edellyttävät asioiden etsimistä, kuten sanan etsimistä sanakirjasta. Jos sanakirja on kaksi kertaa suurempi, siinä on kaksi kertaa enemmän sanoja kuin alkuperäisessä sanakirjassa. Jonkin asian etsiminen vie vain yhden askeleen enemmän. Algoritmi hakujen tekemiseen on yksinkertainen. Sanakirjan keskellä oleva sana on joko ennen tai jälkeen etsittävän termin, jos sanat eivät täsmää. Jos se on ennen, termin on oltava sanakirjan toisella puoliskolla. Jos se on sanan jälkeen, sen on oltava ensimmäisellä puoliskolla. Näin ongelma-avaruus puolittuu jokaisella askeleella, kunnes sana tai määritelmä löytyy. Tätä kutsutaan yleisesti logaritmiseksi monimutkaisuudeksi.
Eksponentiaalinen monimutkaisuus
On ongelmia, jotka kasvavat hyvin nopeasti. Yksi tällainen ongelma tunnetaan nimellä travelling salesman -ongelma. Myyjän on kierrettävä tietty määrä kaupunkeja. Jokaisessa kaupungissa pitäisi käydä vain kerran, matkan pituuden (tai kustannusten) pitäisi olla mahdollisimman pieni, ja myyjän pitäisi päätyä sinne, mistä hän lähti. Tämä ongelma on eksponentiaalisen monimutkainen. Huomioon on otettava n faktoriaalista mahdollisuutta. Yhden kaupungin lisääminen (n:stä n+1:een) lisää mahdollisuuksien lukumäärän (n+1:llä). Useimmat mielenkiintoiset ongelmat ovat näin monimutkaisia.
