Versiunea scurtă este că este un termen de știința calculatoarelor, care s-a întâmplat să fie suficient de scurt încât să-mi placă ca nume de domeniu. În ciuda a ceea ce vă pot spune alții, nu este o ortografie greșită a lui „login”. De asemenea, se pronunță ca „log” urmat de litera „n”.
Versiunea lungă este că este termenul folosit pentru a descrie o clasă de algoritmi foarte eficienți.Dacă îmi permiteți o scurtă lecție…
Complexitate temporală
În informatică, algoritmii sunt adesea comparați prin cantitatea de timp sau de memorie pe care o consumă pentru a îndeplini o sarcină. Pentru ca aceste comparații să fie echitabile și ușor de înțeles, le analizăm pe baza relației dintre mărimea sarcinii și numărul de pași necesari pentru a îndeplini sarcina.
De exemplu, să presupunem că doriți să calculați media unei liste de valori numerice. Pentru a face acest lucru, ar trebui să adunați toate numerele și apoi să le împărțiți la numărul de valori pe care le aveți. Numărul de pași este direct legat de numărul de valori: dacă ați dublat numărul de valori pentru a face media, vă așteptați să dureze de două ori mai mult. Acesta este un exemplu de complexitate liniară: pe măsură ce numărul de elemente (prescurtat n)crește, timpul de finalizare a sarcinii crește în același ritm.
Cert este că puteți face mult mai rău decât un timp liniar; multe sarcini necesită un timp polinomial sau chiar exponențial pentru a fi finalizate! Sortarea listelor de numere este un bun exemplu; trebuie să faceți mai multe treceri peste date pentru a cerne totul într-o ordine finală.
Există însă și unii algoritmi care sunt mai buni decât timpul liniar. Luați în considerare un joc de ghicit în care un om se gândește la un numărîntre 1 și 100, iar calculatorul trebuie să ghicească care este acesta. În cazul în care calculatorul ghicește greșit, omul îi spune calculatorului dacă răspunsul este „mai mare” sau „mai mic” decât cel ghicit. Prin alegerea cu grijă a presupunerilor, această informație permite calculatorului să elimine jumătate din numerele rămase la fiecare presupunere (alegând întotdeauna un număr aflat la mijlocul setului de numere posibile).
Pentru că fiecare presupunere împarte în jumătate numărul rămas, aceste jumătăți repetate se compun și creează un exponent invers: un alogaritm. Efectiv, numărul de pași pentru a rezolva problemacrește liniar pe măsură ce spațiul problemei crește exponențial. Gândit altfel, dublarea dimensiunii problemei duce la un singur pas suplimentar (comparați acest lucru cu un algoritm liniar, unde dublarea dimensiunii problemei dublează și numărul de pași). Abreviem această relație ca logn, arătând că pe măsură ce n (dimensiunea problemei) devine mai mare, numărul de pași este doar logaritmul acestui număr.
Atunci, algoritmii logaritmici sunt foarte eficienți și bine cotați.M-am gândit că ar fi amuzant să-mi numesc domeniul după ei.