Den korte version er, at det er et nørdet datalogisk begreb, som tilfældigvis også var kort nok til, at jeg kunne lide det som domænenavn. Uanset hvad andre kan fortælle dig, er det ikke en stavefejl af “login”. Jeg plejer også at udtale det som “log” efterfulgt af bogstavet “n”.
Den lange version er, at det er et udtryk, der bruges til at beskrive en klasse af meget effektive algoritmer.Hvis du vil give mig en kort lektion…
Tidskompleksitet
I datalogi sammenlignes algoritmer ofte efter den tid eller hukommelse, de bruger på at udføre en opgave. For at gøre disse sammenligninger retfærdige og lette at forstå, analyserer vi dem på grundlag af forholdet mellem opgavens størrelse og det antal trin, der kræves for at udføre opgaven.
Så lad os f.eks. antage, at du ønsker at beregne et gennemsnit af en liste med numeriske værdier. For at gøre det skal du lægge alle tallene sammen og derefter dividere med det antal værdier, du havde. Antallet af trin er direkte relateret til antallet af værdier: hvis du fordobler antallet af værdier, som du skal beregne gennemsnittet af, skal du forvente, at det tager dobbelt så lang tid. Dette er et eksempel på lineær kompleksitet: efterhånden som antallet af elementer (forkortet n) vokser, vokser tiden til at udføre opgaven med samme hastighed.
Du kan helt sikkert gøre det meget værre end lineær tid; mange opgaver kræver polynomial eller endog eksponentiel tid at udføre! Sortering af lister med tal er et godt eksempel; man skal foretage flere gennemgange af dataene for at sortere alt i en endelig rækkefølge.
Der findes imidlertid også nogle algoritmer, som er bedre end lineær tid. Tænk på et gættespil, hvor et menneske tænker på et tal mellem 1 og 100, og computeren skal gætte, hvad det er. Hvis computeren gætter forkert, fortæller mennesket computeren, om svaret er “højere” eller “lavere” end gættet. Ved at vælge gæt med omhu giver denne oplysning computeren mulighed for at fjerne halvdelen af de resterende tal ved hvert gæt (ved altid at vælge et tal i midten af de mulige tal).
Da hvert gæt deler den resterende talpulje i to dele, sammensættes disse gentagne halveringer og skaber en omvendt eksponent: en alogaritme. Det betyder, at antallet af trin til løsning af problemet vokser lineært i takt med, at problemrummet vokser eksponentielt. På en anden måde betragtet resulterer en fordobling af problemets størrelse kun i et enkelt ekstra trin (sammenlign dette med en lineær algoritme, hvor en fordobling af problemets størrelse også fordobler antallet af trin). Vi forkorter dette forhold til logn, hvilket viser, at når n (problemets størrelse) bliver større, er antallet af trin kun logaritmen af dette tal.
Logaritmiske algoritmer er således meget effektive og velanskrevne, og jeg syntes, det ville være sjovt at opkalde mit domæne efter dem.