Algorithmen-Effizienz und Laufzeit
Ein Algorithmus braucht fĂźr jede EingabegrĂśĂe n etwa 3¡n Schritte. Welche O-Notation beschreibt sein Wachstum?
Erklärung: Die O-Notation beschreibt das Wachstumsverhalten bei steigender EingabegrĂśĂe â konstante Faktoren wie die 3 lässt man weg. 3¡n wächst linear, also O(n). O(3n) schreibt man deshalb nicht, und O(nÂł) wäre kubisches Wachstum.
Welche Laufzeit hat ein Algorithmus, der eine sortierte Liste mit binärer Suche durchsucht?
Erklärung: Die binäre Suche halbiert den Suchbereich bei jedem Schritt, daher ist die Laufzeit O(log n) â viel schneller als lineare Suche O(n).
Ein Algorithmus mit O(n²) ist fĂźr groĂe Datenmengen effizienter als einer mit O(n log n).
Erklärung: Falsch. O(n²) wächst viel schneller als O(n log n). Bei 1.000 Elementen: n² = 1.000.000 Schritte, n¡log(n) â 10.000 Schritte.
Ein Algorithmus, der immer gleich lang braucht, egal wie groĂ die Eingabe ist, hat die Laufzeit O(___).
Erklärung: O(1) bedeutet konstante Laufzeit â z. B. Zugriff auf ein Array-Element Ăźber den Index. Die EingabegrĂśĂe spielt keine Rolle.
Ordne die Laufzeiten von schnell (effizient) nach langsam.
Erklärung: O(1) = konstant < O(log n) = logarithmisch < O(n) = linear < O(n²) = quadratisch. Je schneller das Wachstum, desto langsamer der Algorithmus bei groĂen Eingaben.
Welche Laufzeit hat Bubble Sort im schlimmsten Fall?
Erklärung: Bubble Sort vergleicht in jedem Durchlauf benachbarte Elemente. Im schlimmsten Fall (umgekehrt sortierte Liste) benÜtigt er n¡(n-1)/2 Vergleiche = O(n²).
Welcher Sortieralgorithmus hat eine durchschnittliche Laufzeit von O(n log n)?
Erklärung: Merge Sort teilt die Liste rekursiv in Hälften und fßgt sie sortiert zusammen. Die Laufzeit ist immer O(n log n), auch im schlimmsten Fall.
Lineare Suche erfordert, dass die Liste sortiert ist.
Erklärung: Falsch. Lineare Suche prßft jedes Element nacheinander und funktioniert auch in unsortierten Listen. Binäre Suche erfordert eine sortierte Liste.
Die lineare Suche sucht die Zahl 7. In welcher Liste ist das ihr Best Case?
Erklärung: Der Best Case ist die gĂźnstigste Eingabe: Steht die 7 ganz vorn, ist die Suche nach einem Schritt fertig. Steht sie ganz hinten (â3, 9, 1, 7"), ist das der Worst Case â die langsamste mĂśgliche AusfĂźhrung.
Ein Algorithmus, der die Liste bei jedem Schritt halbiert, hat typischerweise eine Laufzeit von O(___).
Erklärung: Halbierung bei jedem Schritt ergibt logarithmisches Wachstum: logâ(1024) = 10, d. h. nur 10 Schritte fĂźr 1024 Elemente.
Ein Programm mit Laufzeit O(n²) braucht fßr 1.000 Datensätze 1 Sekunde. Wie lange braucht es ungefähr fßr 1.000.000 Datensätze?
Erklärung: Bei O(n²) wächst die Zeit mit dem Quadrat â 1.000-mal mehr Daten bedeuten 1.000² = 1.000.000-mal mehr Zeit. Genau deshalb zählt Effizienz â bei groĂen Datenmengen wird ein ineffizienter Algorithmus praktisch unbrauchbar. â1.000 Sekunden" wäre lineares Denken.
Ein Algorithmus mit Laufzeit O(2âż) braucht fĂźr n = 10 rund 1.000 Schritte. Wie viele Schritte braucht er fĂźr n = 20?
Erklärung: O(2âż) ist exponentielles Wachstum â jedes zusätzliche Element verdoppelt die Schrittzahl. Von n = 10 auf n = 20 sind das 10 Verdopplungen, also Faktor 1.024. âRund 2.000" wäre lineares, ârund 4.000" quadratisches Wachstum.
Quicksort hat im Average Case eine Laufzeit von O(n log n).
Erklärung: Richtig. Quicksort wählt ein Pivot-Element und teilt die Liste. Im Durchschnitt ist er O(n log n), im Worst Case jedoch O(n²).
Merge Sort legt beim Sortieren von n Zahlen eine Hilfsliste mit n Plätzen an. Welche Speicherkomplexität hat er dadurch?
Erklärung: Speicherkomplexität beschreibt den zusätzlichen Speicher, den ein Algorithmus braucht. Die Hilfsliste hat n Plätze, also O(n). O(1) hieĂe konstanter Zusatzspeicher; O(n log n) ist die Laufzeit von Merge Sort, nicht sein Speicherbedarf.