Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:big_o:start [23.07.2020 11:29] – ["Typische" Laufzeiten von Algorithmen] 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? Dazu betrachten wir die folgende Tabelle, in der die "worst case"-Zeiten dargestellt sind.
+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 ^
+^ Zahl der Elemente  ^ Einfache Suche  ^ Binäre Suche  ^
-|100  | 100ms  | 7ms |
+| 100                | 100ms           | 7ms           |
-|10.000| 10 Sekunden | 14ms |
+| 10.000             | 10 Sekunden     | 14ms          |
-|1.000.000.000 | 11 Tage | 32ms |
+| 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**.
+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>
@@ Zeile 34: / Zeile 34: @@
   - Du zeichnest mit einem Stift nacheinander Kästchen für Kästchen auf das Blatt.
-  - Du faltest das Blatt "über Kreuz" jeweils auf seine Hälfte und verwendest die Faltmarken als Ränder der Quadrate.
+  - Du faltest das Blatt jeweils auf seine Hälfte und verwendest die Faltmarken als Ränder der Quadrate.
-  * Überlege zunächst, wieviele Operationen du für 16 Kästchen jeweils benötigst.
+  * Überlege zunächst, wie viele Operationen du für 16 Kästchen jeweils benötigst.
-  * Wieviele Operationen benötigt man, um 32 oder 64 Kästchen zu erzeugen?
+  * Wie viele Operationen benötigt man, um 32 oder 64 Kästchen zu erzeugen?
   * Wie effizient sind die beiden Vorgehensweisen in der Landau-Notation?
-  * Josephins 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?
+  * 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) - "logarithnische Laufzeit"//, z.B. die binäre Suche
+  * //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.