Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:big_o:start [23.07.2020 11:11] – sbel
+++ faecher:informatik:oberstufe:algorithmen:big_o:start [21.02.2024 10:28] (aktuell) – [Tabelle] Marco Kuemmel
@@ Zeile 6: / Zeile 6: @@
 <WRAP center round info 95%>
-Darum einigt man sich, dass man bei der Beurteilung von Algorithmen bevorzugt den schlechtesten Fall ("worst case") betrachtet, um einen Eindruck zu bekommen, wie effektiv ein Algorithmus arbeitet
+Darum einigt man sich, dass man bei der Beurteilung von Algorithmen bevorzugt den schlechtesten Fall ("worst case") betrachtet, um einen Eindruck zu bekommen, wie effektiv ein Algorithmus arbeitet.
 </WRAP>
-Der schlechteste Fall bei der binären Suche dauert 7ms, also 15 mal so lang. Die binäre Suche ist also 15 mal schneller als die einfache suche?! Stimmt das?
+Der schlechteste Fall bei der binären Suche dauert 7ms, also nur 1/15 mal so lang. Die binäre Suche ist also 15 mal schneller als die einfache Suche?! Stimmt das? Dazu betrachten wir die folgende Tabelle, in der die "worst case"-Zeiten dargestellt sind.
+^ Zahl der Elemente  ^ Einfache Suche  ^ Binäre Suche  ^
+| 100                | 100ms           | 7ms           |
+| 10.000             | 10 Sekunden     | 14ms          |
+| 1.000.000          | 11 Tage         | 32ms          |
+Man sieht, dass die Laufzeiten **mit der Zunahme der Zahl der Elemente sehr unterschiedlich zunehmen**.
+<WRAP center round info 95%>
+Um diesen Umstand darzustellen, verwendet man die **Landau-Notation** (oder auch "Big-O-Notation). Die Landau Notation ermöglicht es, die Anzahl der Operationen die Algorithmen zur Lösung eines Problems benötigen zu vergleichen - sie teilt dir mit, wie schnell die Zahl der Operationen des Algorithmus **anwächst**.
+</WRAP>
+Für unser Beispiel oben:
+^Einfache Suche ^ Binäre Suche ^
+| O(n)  | O(log n) |
+===== Übung =====
+Du sollst auf einem  Blatt Papier 16 rechteckige Kästchen erzeugen. Wie effizient sind die folgenden beiden Algorithmen?
+  - Du zeichnest mit einem Stift nacheinander Kästchen für Kästchen auf das Blatt.
+  - Du faltest das Blatt jeweils auf seine Hälfte und verwendest die Faltmarken als Ränder der Quadrate.
+  * Überlege zunächst, wie viele Operationen du für 16 Kästchen jeweils benötigst.
+  * Wie viele Operationen benötigt man, um 32 oder 64 Kästchen zu erzeugen?
+  * Wie effizient sind die beiden Vorgehensweisen in der Landau-Notation?
+  * Josephine sagt: "Stopp! - wir haben doch gar nicht festgelegt, was beim Zeichnen einer Operation entspricht. Ist das das Zeichnen eines Rechtecks oder das Ziehen einer Linie? Im zweiten Fall benötigt das Zeichnen eines Rechtecks ja 4 Operationen!" Was sagst du dazu?
+====== "Typische" Laufzeiten von Algorithmen ======
+  * //O(log n) - "logarithmische Laufzeit"//, z. B. die binäre Suche
+  * //O(n) - "lineare Laufzeit"//, z. B. die einfache Suche
+  * //O(n*log n)//, ein schneller Sortieralgorithmus
+  * //O(n^2)//, ein langsamer Sortieralgorithmus
+  * //O(n!)//, ein sehr langsamer Algorithmus (Problem des Handlungsreisenden, [[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden|1]][[https://mathepedia.de/Problem_des_Handlungsreisenden.html|2]])
+====== Zusammenfassung ======
+<WRAP center round info 95%>
+  * Die Geschwindigkeit eines Algorithmus wird **nicht** als Zeit (z. B. in Sekunden) angegeben, sondern durch die Betrachtung der **Zunahme der Anzahl der Operationen**.
+  * Wir schauen, wie schnell die Laufzeit zunimmt, wenn die Größe der Eingabe zunimmt.
+  * Die Laufzeit wird in der Landau Notation aufgeschrieben
+</WRAP>
+====== Aufgaben ======
+Gib die Laufzeit der folgenden Probleme in Landau-Notation an (das Telefonbuch ist aus Papier).
+  * Finde die Telefonnummer einer Person mit bekanntem Namen
+  * Finde den Namen einer Person anhand einer bekannten Telefonnummer.
+  * Es sollen alle Namen und Telefonnummern eingelesen werden.
+  * Es sollen alle Namen und Telefonnummern von Personen eingelesen werden, deren Namen mit A beginnt.