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:16] – [Die Landau Notation im Detail] sbel
@@ Zeile 55: / Zeile 55: @@
 Darf man das?
-Dazu vergleichen wir nochmal gedanklich die einfach Suche und die binäre Suche und ergänzen die Laufzeiten mit realen Zeitfaktoren:
+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 61: @@
+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.
+++++