De korte versie is dat het een nerderig computerwetenschappelijk begrip is dat toevallig ook kort genoeg was om het als domeinnaam te kunnen gebruiken. Ondanks wat anderen je misschien vertellen, is het geen spelfout van “login”. Je spreekt het ook uit als “log” gevolgd door de letter “n”.
De lange versie is dat het de term is die wordt gebruikt om een klasse van zeer efficiënte algoritmen te beschrijven.
Tijdcomplexiteit
In de computerwetenschap worden algoritmen vaak vergeleken aan de hand van de hoeveelheid tijd of geheugen die ze nodig hebben om een taak uit te voeren. Om deze vergelijkingen eerlijk en begrijpelijk te maken, analyseren we ze op basis van de verhouding tussen de omvang van de taak en het aantal stappen dat nodig is om de taak te volbrengen.
Voorbeeld: je wilt het gemiddelde berekenen van een lijst met numerieke waarden. Om dat te doen, moet u alle getallen optellen en delen door het aantal waarden. Het aantal stappen is direct gerelateerd aan het aantal waarden: als je het aantal te middelen waarden verdubbelt, zou je verwachten dat het twee keer zo lang duurt. Dit is een voorbeeld van lineaire complexiteit: als het aantal items (afgekort als n) toeneemt, neemt de tijd om de taak te voltooien met dezelfde snelheid toe.
Het kan zeker veel erger dan lineaire tijd; veel taken vereisen een polynomiale of zelfs exponentiële tijd om te voltooien! Het sorteren van lijsten met getallen is een goed voorbeeld; je moet de gegevens meerdere malen passeren om alles in een definitieve volgorde te sorteren.
Echter zijn er ook algoritmen die beter zijn dan lineaire tijd. Denk aan een raadspel waarbij een mens een getal tussen 1 en 100 bedenkt, en de computer moet raden wat het is. Als de computer verkeerd raadt, vertelt de mens de computer of het antwoord “hoger” of “lager” is dan het geraden getal. Door zorgvuldig te raden kan de computer met deze informatie bij elke gok de helft van de overgebleven getallen elimineren (door steeds een getal in het midden van de mogelijke getallen te kiezen)
Omdat elke gok de overgebleven getallenpool in tweeën deelt, vormen de herhaalde halvingen een inverse exponent: een logaritme. In feite groeit het aantal stappen om het probleem op te lossen lineair naarmate de probleemruimte exponentieel groeit. Omgekeerd betekent een verdubbeling van de probleemgrootte slechts één extra stap (vergelijk dit met een lineair algoritme, waar een verdubbeling van de probleemgrootte ook een verdubbeling van het aantal stappen inhoudt). We korten deze relatie af met logn, waarmee wordt aangegeven dat als n (de probleemgrootte) groter wordt, het aantal stappen slechts de logaritme van dat getal is.
Dus logaritmische algoritmen zijn zeer efficiënt en goed aangeschreven. Het leek me leuk om mijn domein ernaar te noemen.