Laskennallinen monimutkaisuusteoria keskittyy laskennallisten ongelmien luokittelemiseen niiden resurssien käytön mukaan ja näiden luokkien suhteuttamiseen toisiinsa. Laskennallinen ongelma on tietokoneen ratkaisema tehtävä. Laskentaongelma voidaan ratkaista käyttämällä mekaanisesti matemaattisia vaiheita, kuten algoritmia.
Mitä tarkoitat algoritmin monimutkaisuudella?
Algoritmin monimutkaisuus on mitta, kuinka paljon aikaa ja/tai tilaa algoritmi vaatii tietyn kokoiselle syötteelle (n).
Mitä on tietorakenteen algoritminen monimutkaisuus?
Algoritminen monimutkaisuus on mitta siitä, kuinka kauan algoritmin valmistuminen kestäisi syötteellä, jonka koko on n. Jos algoritmin on skaalattava, sen tulee laskea tulos äärellisen ja käytännöllisen aikarajan sisällä jopa suurilla n:n arvoilla. Tästä syystä monimutkaisuus lasketaan asymptoottisesti, kun n lähestyy ääretöntä.
Miksi algoritminen monimutkaisuus on tärkeää?
Tietokonetieteilijät käyttävät matemaattisia monimutkaisia mittareita, jotka antavat heidän ennustaa ennen koodin kirjoittamista, kuinka nopeasti algoritmi toimii ja kuinka paljon muistia se vaatii. Tällaiset ennusteet ovat tärkeitä oppaita ohjelmoijille, jotka toteuttavat ja valitsevat algoritmeja tosielämän sovelluksiin.
Miten algoritminen monimutkaisuus lasketaan?
Jokaiselle silmukalle selvitetään niiden sisällä olevan lohkon ajoaika ja kerrotaan se määrällä, kuinka monta kertaa ohjelmatoista silmukka. Kaikilla silmukoilla, jotka kasvavat suhteessa syötteen kokoon, on lineaarinen aikakompleksisuus O(n). Jos silmukat vain puolet taulukosta, se on silti O(n).
