Big O Notation/ Komplexität

[Mimi0404]

Hallo Miteinander

 

Aktuell besprechen wir in den Vorlesungen Big O Notationen. Ich stollpere nur beim Verständnis von O(log n). Ich versteh nicht ganz wie man auf O(log n) kommt und was O(log n) Aussagen soll.

Bei O(n²) bedeutet das ja, dass die Komplexität quadratisch zu der Eingabemenge wächst. Bei log n erschließt mir das nicht.

 

Schonmal danke im Voraus !

[Shannon]

O(n) meint gehe jedes Element einmal durch.

O(n^2) meint gehe jedes Element und dann nochmal jedes Element einmal durch, also zwei Schleifen ineinander.

O(log(n)) meint praktisch meist log2(n). Das kommt zum Beispiel bei einem Binärbaum vor. Wenn der Binärbaum n=256 Elemente halten kann so findest du ein Element (zumindest in einem perfekt balancierten und ausgelasteten Binärbaum) in maximal 8 schritten, also log2(256).

 

Kommt häufig auch bei divide and conquer Sortieralgorithmen vor. Genau wie bei "ein element runter gehen" im Binärbaum halbiert sich die Anzahl der Elemente bei jeder Iteration, also log2(n).

 

Grüße

Bearbeitet 13. November 2023 von Shannon

[Mimi0404]

Lieben Danke erstmal@Shannon!!

Da kommt mir halt die Frage, wann ich O(log(n)) erkenne. Bei O(n²) sind es meistens zwei Schleifen , bei O(n³) dann 3.

Wie erkenne ich ein O(log(n)) Komplexität?

Vielen Dank nochmal!

[Shannon]

Hallo @Mimi0404,

das ist nicht ganz so einfach, man kann nur nach bestimmten Mustern ausschau halten. Beispielsweise wäre das:

• Unterteilen des Suchbereichs in mehrere Untersuchbereiche (z.B. immer zwei bei jeder Iteration)
• Wiederholte Multiplikation oder Division durch einen konstanten Faktor
• Variable verdoppelt/halbiert sich bei jedem Durchlauf (z.B. als Modifikator in der for i=i*2)
• Manchmal hat man das bei rekursiven Funktionen (vgl. Divide and Conquer Sortieralgorithmen als rekursive Implementierung)
• Bei Baumstrukturen
• Bei dem Arbeiten mit anderen Zahlensystemen, z.B. für jedes Bit in der Binärdarstellung (Bsp. Square and Muliply Algorithmus aus der Kryptographie)

Das wären die Fälle, die mir aktuell einfallen. Ich vermute in einer Klausuraufgabe würde das mit etwas erfahrung aber auch gut deutlich werden, wenn etwas logarithmisch ist.

Die allgemeine Lösung wäre genau nachzuvollziehen, wie der Code allgemein verläuft. Dort erkennt man es am besten.

Grüße

Bearbeitet 13. November 2023 von Shannon