A rövid változat az, hogy ez egy stréber informatikai kifejezés, amely elég rövid ahhoz, hogy domainnévként is megtetszett. Annak ellenére, amit mások mondanak, ez nem a “login” elírása. A hosszú változat az, hogy ez a kifejezés a nagy hatékonyságú algoritmusok egy osztályának leírására szolgál.Ha megengedsz nekem egy rövid leckét…
Az időbonyolultság
A számítástechnikában az algoritmusokat gyakran az általuk egy feladat elvégzéséhez felhasznált idő vagy memória mennyisége alapján hasonlítják össze. Annak érdekében, hogy ezek az összehasonlítások igazságosak és könnyen érthetőek legyenek, a feladat mérete és a feladat elvégzéséhez szükséges lépések száma közötti kapcsolat alapján elemezzük őket.
Tegyük fel például, hogy egy numerikus értékekből álló listát szeretnénk átlagolni. Ehhez össze kell adnia az összes számot, majd osztania kell az értékek számával. A lépések száma közvetlenül függ az értékek számától: ha megdupláznád az értékek számátaz átlagoláshoz kétszer annyi időre számíthatnál. Ez egy példa a lineáris bonyolultságra: ahogy az elemek száma (rövidítve n)nő, a feladat elvégzéséhez szükséges idő is ugyanilyen ütemben növekszik.
A lineáris időnél természetesen sokkal rosszabbat is elérhetünk; sok feladat elvégzéséhez polinomiális vagy akár exponenciális időre van szükség! A számlisták rendezése jó példa erre; többször át kell mennünk az adatokon, hogy mindent a végső sorrendbe szitáljunk.
Valamint vannak olyan algoritmusok is, amelyek jobbak a lineáris időnél. Gondoljunk egy tippelős játékra, ahol az ember kitalál egy számot egy és 100 között, és a számítógépnek kell kitalálnia, hogy mi az. Ha a számítógép rosszul tippel, az ember megmondja a számítógépnek, hogy a válasz “nagyobb” vagy “kisebb”, mint a tipp. A találgatások körültekintő megválasztásával ez az információ lehetővé teszi a számítógép számára, hogy minden egyes találgatással a megmaradó számok felét eltüntesse (mindig a lehetséges számhalmaz közepén lévő számot választva).
Mivel minden egyes találgatás felezi a megmaradó számhalmazt, ezek az ismételt felezések összeadódnak, és egy fordított exponenciát: egy algaritmust hoznak létre. Gyakorlatilag a probléma megoldásához szükséges lépések száma lineárisan nő, ahogy a problématér exponenciálisan növekszik. Másképp fogalmazva, a probléma méretének megduplázása csak egyetlen további lépést eredményez (hasonlítsuk ezt össze egy lineáris algoritmussal, ahol a probléma méretének megduplázása a lépések számát is megduplázza). Ezt az összefüggést logn-nek rövidítjük, ami azt mutatja, hogy ahogy n (a probléma mérete) nő, a lépések száma csak ennek a számnak a logaritmusa.
A logaritmikus algoritmusok tehát rendkívül hatékonyak és elismertek.Úgy gondoltam, jó móka lenne, ha a tartományomat róluk nevezném el.