Vad är logn?

Den korta versionen är att det är en nördig datavetenskapsterm som också råkade vara tillräckligt kort för att jag gillade det som domännamn. Trots vad andra kan säga är det inte en felstavning av ”login”. Dessutom brukar det uttalas som ”log” följt av bokstaven ”n”.

Den långa versionen är att det är en term som används för att beskriva en klass av högeffektiva algoritmer.Om du vill ge mig en kort lektion…

Tidskomplexitet

I datavetenskapen jämförs algoritmer ofta med hjälp av den tid eller det minne som de tar i anspråk för att utföra en uppgift. För att göra dessa jämförelser rättvisa och lätta att förstå analyserar vi dem utifrån förhållandet mellan uppgiftens storlek och det antal steg som krävs för att utföra uppgiften.

Föreställ dig till exempel att du vill göra ett genomsnitt av en lista med numeriska värden. För att göra det skulle du behöva addera alla siffror och sedan dividera med antalet värden du hade. Antalet steg är direkt relaterat till antalet värden: om du fördubblar antalet värden för att göra ett medelvärde kan du förvänta dig att det tar dubbelt så lång tid. Detta är ett exempel på linjär komplexitet: när antalet objekt (förkortat n) ökar, ökar tiden för att slutföra uppgiften i samma takt.

Det går säkert att göra mycket sämre än linjär tid; många uppgifter kräver polynomial eller till och med exponentiell tid att slutföra! Att sortera listor med siffror är ett bra exempel; du måste göra flera överfarter över datamaterialet för att sålla allt i en slutlig ordning.

Det finns emellertid också vissa algoritmer som är bättre än linjär tid. Tänk på en gissningslek där en människa tänker på ett tal mellan ett och 100, och datorn måste gissa vad det är. Om datorn gissar fel berättar människan för datorn om svaret är ”högre” eller ”lägre” än gissningen. Genom att välja gissningar med omsorg gör denna information det möjligt för datorn att eliminera hälften av de återstående siffrorna med varje gissning (genom att alltid välja ett nummer i mitten av de möjliga siffrorna).

Eftersom varje gissning halverar den återstående sifferpoolen, sammansätts dessa upprepade halveringar och skapar en omvänd exponent: en alogaritm. Antalet steg för att lösa problemet växer linjärt i takt med att problemområdet växer exponentiellt. Om man tänker på ett annat sätt resulterar en fördubbling av problemets storlek i endast ett enda ytterligare steg (jämför detta med en linjär algoritm, där en fördubbling av problemets storlek också fördubblar antalet steg). Vi förkortar detta förhållande med logn, vilket visar att när n (problemets storlek) blir större är antalet steg endast logaritmen av detta antal.

Därmed är logaritmiska algoritmer mycket effektiva och välrenommerade.Jag tyckte att det skulle vara roligt att döpa min domän efter dem.

Lämna ett svar

Din e-postadress kommer inte publiceras.