Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:05] – [Die Landau Notation im Detail] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:32] – [Faktoren spielen doch eine Rolle?] sbel
@@ Zeile 31: / Zeile 31: @@
 ===== Die Landau Notation im Detail =====
+==== Faktoren spielen keine Rolle? ====
 Die Landau Notation unterschlägt Konstanten - wenn man schreibt O(n) meint man eigentlich O(c*n). Das kann man sich am Beispiel eine Methode klar machen, die die Elemente eines Arrays ausgibt:
@@ Zeile 55: / Zeile 58: @@
 Darf man das?
-Dazu vergleichen wir nochmal gedanklich die einfach Suche und die binäre Suche und ergänzen die Laufzeiten mit realen Zeitfaktoren:
+==== Suchvergleich mit Faktoren ====
+Dazu vergleichen wir nochmal gedanklich die **einfache Suche** und die **binäre Suche** und ergänzen die Laufzeiten mit realen Zeitfaktoren:
 ^ Einfache Suche ^ Binäre Suche ^
@@ Zeile 61: / Zeile 67: @@
+Die einfache Suche läuft also beispielsweise auf einem sehr viel schnelleren Rechner, so dass pro Element lediglich 10 Millisekunden hinzukommen - die binäre Suche läuft auf einem langsameren Rechner, die Zeit wächst hier zwar logarithmisch aber mit einem Faktor von 1 Sekunde.
+Dieser Vorteil wird jedoch von einer großen Anzahl von Elementen zunichte gemacht.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+Wie lange dauert es, eine Liste mit 4 Milliarden Elementen mit den beiden Algorithmen zu durchsuchen?
+++++ Lösung |
+| Einfache Suche | 10ms * 4 Milliarden | 462 Tage |
+| Binäre Suche | 1Sekunde * log(4Milliarden) | 35 Sekunden |
+Beachte: der Logarithmus in O(log n) wird zur Basis 2 berechnet.
+++++
+<WRAP center round important 95%>
+Wenn die **Anzahl der Elemente veränderlich** ist, spielen Faktoren bei der Landau Notation keine Rolle. Jeder Vorteil eines Faktors wird bei einem Algorithmus mit besserer Laufzeit bei genügend großer Anzahl der Elemente wieder eingeholt.
+</WRAP>
+==== Faktoren spielen doch eine Rolle? ====
+Manchmal spielen Faktoren aber eben doch eine Rollen - nämlich dann, wenn die Anzahl der Elemente beim Vergleich zweier Algorithmen vorgegeben ist. Das ist beispielsweise dann der Fall, wenn wir ein und dasselbe Array mit zwei unterschiedlichen Sortierverfahren sortieren wollen: Wenn die Laufzeit von Quicksort sich in Abhängigkeit des gewählten Pivotelements verändert, spielt der Faktor eine Rolle.
+Die Konstante von Quicksort ist kleiner als die von Mergesort. Wenn beide Algorithmen eine Laufzeit von O(n log n) benötigen, ist Quicksort also schneller, wenn sich bei einer festen Anzahl von Elementen aber die Laufzeit von Quicksort hin zu O(n<sup>2</sup>) verschiebt, kann es sein, dass Mergesort irgendwann schneller ist, weil Mergesort //immer// die Laufzeit O(n log n) hat.
+===== Average Case und Worst Case bei Quicksort =====