Zkrácená verze je, že se jedná o geekovský termín z počítačové vědy, který je také dost krátký na to, aby se mi líbil jako název domény. Navzdory tomu, co vám řeknou ostatní, nejde o překlep slova „login“. Také se to obvykle vyslovuje jako „log“ následované písmenem „n“.
Dlouhá verze je, že je to termín používaný k popisu třídy vysoce efektivních algoritmů.
Časová složitost
V informatice se algoritmy často porovnávají podle množství času nebo paměti, které spotřebují na provedení úlohy. Aby tato srovnání byla spravedlivá a srozumitelná, analyzujeme je na základě vztahu mezi velikostí úlohy a počtem kroků potřebných k jejímu dokončení.
Předpokládejme například, že chcete zprůměrovat seznam číselných hodnot. Abyste to mohli udělat, museli byste sečíst všechna čísla a pak je vydělit počtem hodnot. Počet kroků přímo souvisí s počtem hodnot: pokud byste zdvojnásobili počet hodnotpro zprůměrování, očekávali byste, že to bude trvat dvakrát déle. To je příklad lineární složitosti: s rostoucím počtem položek (zkráceně n) roste stejnou rychlostí i čas potřebný k dokončení úlohy.
Jistě lze dosáhnout mnohem horšího než lineárního času; mnoho úloh vyžaduje k dokončenípolynomiální nebo dokonce exponenciální čas! Dobrým příkladem je třídění seznamů čísel; musíte provést několik průchodů nad daty, abyste vše roztřídili do konečného pořadí.
Existují však i algoritmy, které jsou lepší než lineární čas. Vezměme si tipovací hru, kdy člověk vymyslí číslo mezi 1 a 100 a počítač má uhodnout, co to je. Pokud počítač hádá špatně, člověk počítači řekne, zda je odpověď „vyšší“ nebo „nižší“ než odhad. Tím, že se hádání volí opatrně, umožňuje tato informace počítači při každém hádání eliminovat polovinu zbývajících čísel (tím, že vždy vybere číslo uprostřed možné množiny čísel).
Protože každé hádání dělí zbývající množinu čísel na polovinu, opakované poloviční hádání se skládá a vytváří inverzní exponent: alogaritmus. Efektivně počet kroků k vyřešení problémurůstá lineárně s tím, jak exponenciálně roste problémový prostor. Jinak řečeno, zdvojnásobení velikosti problému vede pouze k jednomu dodatečnému kroku (srovnejte to s lineárním algoritmem, kde zdvojnásobení velikosti problému také zdvojnásobí počet kroků). Tento vztah zkracujeme na logn, což ukazuje, že s rostoucím n (velikostí problému) je počet kroků pouze logaritmem tohoto čísla.
Takže logaritmické algoritmy jsou vysoce efektivní a dobře hodnocené. napadlo mě, že by bylo zábavné pojmenovat po nich svou doménu.