Was ist logn?

Die Kurzfassung ist, dass es sich um einen Fachbegriff aus der Informatik handelt, der außerdem so kurz ist, dass er mir als Domänenname gefällt. Ungeachtet dessen, was andere sagen mögen, ist es keine falsche Schreibweise von „Login“. Außerdem spricht man es als „log“ aus, gefolgt vom Buchstaben „n“.

Die lange Version ist, dass es der Begriff ist, der verwendet wird, um eine Klasse hocheffizienter Algorithmen zu beschreiben.

Zeitkomplexität

In der Informatik werden Algorithmen oft anhand der Zeit oder des Speichers verglichen, den sie für die Ausführung einer Aufgabe benötigen. Um diese Vergleiche fair und leicht verständlich zu machen, analysieren wir sie auf der Grundlage des Verhältnisses zwischen der Größe der Aufgabe und der Anzahl der Schritte, die zur Erfüllung der Aufgabe erforderlich sind.

Nehmen wir zum Beispiel an, dass Sie eine Liste numerischer Werte mitteln wollen. Dazu müssten Sie alle Zahlen addieren und dann durch die Anzahl der Werte dividieren, die Sie haben. Die Anzahl der Schritte steht in direktem Zusammenhang mit der Anzahl der Werte: Wenn Sie die Anzahl der zu mittelnden Werte verdoppeln würden, würde es doppelt so lange dauern. Dies ist ein Beispiel für lineare Komplexität: Mit zunehmender Anzahl der Elemente (abgekürzt als n) wächst die Zeit für die Erledigung der Aufgabe mit der gleichen Rate.

Es gibt sicherlich viel schlechtere als lineare Zeit; viele Aufgaben erfordern polynomiale oder sogar exponentielle Zeit zur Erledigung! Das Sortieren von Zahlenlisten ist ein gutes Beispiel; man muss die Daten mehrfach durchgehen, um alles in eine endgültige Reihenfolge zu bringen.

Es gibt jedoch auch einige Algorithmen, die besser sind als lineare Zeit. Man denke an ein Ratespiel, bei dem sich ein Mensch eine Zahl zwischen eins und 100 ausdenkt und der Computer diese Zahl erraten muss. Wenn der Computer falsch rät, sagt der Mensch dem Computer, ob die Antwort „höher“ oder „niedriger“ ist als die Schätzung. Durch eine sorgfältige Auswahl der Tipps kann der Computer mit dieser Information bei jedem Tipp die Hälfte der verbleibenden Zahlen eliminieren (indem er immer eine Zahl in der Mitte der möglichen Zahlenmenge auswählt).

Da jeder Tipp den verbleibenden Zahlenpool halbiert, setzen sich diese wiederholten Halbierungen zusammen und bilden einen Umkehrexponenten: einen Alogarithmus. Effektiv wächst die Anzahl der Schritte zur Lösung des Problems linear, während der Problemraum exponentiell wächst. Anders ausgedrückt: Die Verdoppelung der Problemgröße führt nur zu einem einzigen zusätzlichen Schritt (zum Vergleich: Bei einem linearen Algorithmus verdoppelt sich mit der Verdoppelung der Problemgröße auch die Anzahl der Schritte). Diese Beziehung wird mit logn abgekürzt, um zu zeigen, dass die Anzahl der Schritte mit zunehmender Größe von n (der Problemgröße) nur der Logarithmus dieser Zahl ist.

Logarithmische Algorithmen sind also sehr effizient und angesehen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.