Lyhyesti sanottuna se on nörttimäinen tietotekniikkatermi, joka sattui olemaan myös niin lyhyt, että pidin siitä verkkotunnuksena. Huolimatta siitä, mitä muut sanovat, se ei ole kirjoitusvirhe sanasta ”login”. Lisäksi se lausutaan kuten ”log”, jota seuraa kirjain ”n”.
Pitkä versio on, että se on termi, jota käytetään kuvaamaanluokkaa erittäin tehokkaita algoritmeja.Jos sallitte minulle lyhyen oppitunnin…
Aikakompleksisuus
Tietojenkäsittelytieteessä algoritmeja verrataan usein sen mukaan, kuinka paljon aikaa tai muistia ne kuluttavat jonkin tehtävän suorittamiseen. Jotta nämä vertailut olisivat oikeudenmukaisia ja helposti ymmärrettäviä, analysoimme niitä perustuen tehtävän koon ja tehtävän suorittamiseen tarvittavien vaiheiden määrän väliseen suhteeseen.
Esitettäköön esimerkiksi, että haluaisit laskea keskiarvon numeeristen arvojen luettelosta. Sitä varten sinun pitäisi laskea kaikki luvut yhteen ja jakaa ne sitten arvojen lukumäärällä. Vaiheiden määrä on suorassa suhteessa arvojen määrään: jos keskiarvoistettavien arvojen määrä kaksinkertaistuu, se kestää kaksi kertaa kauemmin. Tämä on esimerkki lineaarisesta monimutkaisuudesta: kun kohteiden määrä (lyhenne n) kasvaa, tehtävän suorittamiseen kuluva aika kasvaa samaa tahtia.
Voit toki pärjätä paljon huonomminkin kuin lineaarisella ajalla; monien tehtävien suorittaminen vaatii polynomaalisen tai jopa eksponentiaalisen ajan! Numeroluetteloiden lajittelu on hyvä esimerkki; sinun täytyy tehdä useita läpikäyntejä datan yli seuloaksesi kaiken lopulliseen järjestykseen.
On kuitenkin olemassa myös joitakin algoritmeja, jotka ovat parempia kuin lineaariaika. Ajatellaan arvauspeliä, jossa ihminen ajattelee luvun yhden ja sadan välillä, ja tietokoneen on arvattava, mikä se on. Jos tietokone arvaa väärin, ihminen kertoo tietokoneelle, onko vastaus ”suurempi” vai ”pienempi” kuin arvaus. Kun arvaukset valitaan huolellisesti, tämä tieto antaa tietokoneelle mahdollisuuden poistaa puolet jäljelle jäävistä luvuista jokaisella arvauksella (valitsemalla aina luvun mahdollisen lukujoukon keskeltä).
Koska jokainen arvaus jakaa jäljelle jäävän numerovalikoiman kahtia, nämä toistuvat puolittamiset yhdistyvät ja muodostavat käänteisen eksponentin: alogaritmin. Todellisuudessa ongelman ratkaisemiseen tarvittavien vaiheiden määrä kasvaa lineaarisesti ongelma-avaruuden kasvaessa eksponentiaalisesti. Toisella tavalla ajateltuna ongelman koon kaksinkertaistaminen johtaa vain yhteen lisävaiheeseen (vertaa tätä lineaariseen algoritmiin, jossa ongelman koon kaksinkertaistaminen kaksinkertaistaa myös vaiheiden määrän). Lyhennämme tätä suhdetta logn:llä, mikä osoittaa, että kun n (ongelman koko) kasvaa, askelten määrä on vain tämän luvun logaritmi.
Logaritmiset algoritmit ovat siis erittäin tehokkaita ja arvostettuja.Ajattelin, että olisi hauska nimetä verkkotunnukseni niiden mukaan.