faecher:informatik:oberstufe:algorithmen:big_o:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:big_o:start [23.07.2020 11:58] – [Aufwandsbeurteilung: Wie "schnell" ist ein Algorithmus?] sbelfaecher:informatik:oberstufe:algorithmen:big_o:start [21.02.2024 10:28] (aktuell) – [Tabelle] Marco Kuemmel
Zeile 6: Zeile 6:
  
 <WRAP center round info 95%> <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> </WRAP>
  
-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.+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**. Man sieht, dass die Laufzeiten **mit der Zunahme der Zahl der Elemente sehr unterschiedlich zunehmen**.
  
 <WRAP center round info 95%> <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> </WRAP>
  
Zeile 34: Zeile 34:
  
   - Du zeichnest mit einem Stift nacheinander Kästchen für Kästchen auf das Blatt.   - 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?   * 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 ====== ====== "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) - "lineare Laufzeit"//, z. B. die einfache Suche
   * //O(n*log n)//, ein schneller Sortieralgorithmus   * //O(n*log n)//, ein schneller Sortieralgorithmus
   * //O(n^2)//, ein langsamer Sortieralgorithmus   * //O(n^2)//, ein langsamer Sortieralgorithmus
Zeile 53: Zeile 53:
  
 <WRAP center round info 95%> <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**.+  * 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.   * Wir schauen, wie schnell die Laufzeit zunimmt, wenn die Größe der Eingabe zunimmt.
-  * Die Laufzeit wird in der Ladau Notation aufgeschrieben+  * Die Laufzeit wird in der Landau Notation aufgeschrieben
 </WRAP> </WRAP>
  
  • faecher/informatik/oberstufe/algorithmen/big_o/start.1595505513.txt.gz
  • Zuletzt geändert: 23.07.2020 11:58
  • von sbel