Algorithmen-Effizienz und Laufzeit

Algorithm Efficiency

Informatik Klasse 11 14 Aufgaben
AlgorithmenKomplexitätWirkungsgrad

Der Aufwand eines Verfahrens misst sich in wesentlichen Schritten statt in Sekunden — unabhängig von der Maschine. Die O-Notation fasst das Wachstum: konstant, logarithmisch, linear, quadratisch, exponentiell; zwischen linearer und binärer Suche oder Bubble Sort und Mergesort liegt genau dieser Unterschied. Zwei Einsichten tragen: Die Laufzeitklasse ist eine Eigenschaft des Verfahrens, nicht des Computers — und zwischen n² und n·log n liegt bei großen Eingaben der Unterschied zwischen Sekunden und Stunden.

Voraussetzungen (1)

Programme Schritt fĂźr Schritt verfolgen
Klasse 9
›

ErmĂśglicht (1)

Komplexität und praktische Grenzen
Klasse 12
›
Leicht
Multiple Choice #1 15s ▶ Testen

Ein Algorithmus braucht für jede Eingabegröße n etwa 3·n Schritte. Welche O-Notation beschreibt sein Wachstum?

  • ● O(n)
  • ○ O(3n)
  • ○ O(nÂł)
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.
Lückentext #2 15s ▶ Testen

Ein Algorithmus, der immer gleich lang braucht, egal wie groß die Eingabe ist, hat die Laufzeit O(___).

✓ Antwort: 1
O(1) bedeutet konstante Laufzeit – z. B. Zugriff auf ein Array-Element über den Index. Die Eingabegröße spielt keine Rolle.
Sortieren #3 25s ▶ Testen

Ordne die Laufzeiten von schnell (effizient) nach langsam.

✓ Antwort: O(1), O(log n), O(n), O(n²)
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.
Wahr / Falsch #4 15s ▶ Testen

Lineare Suche erfordert, dass die Liste sortiert ist.

✓ Falsch
Falsch. Lineare Suche prßft jedes Element nacheinander und funktioniert auch in unsortierten Listen. Binäre Suche erfordert eine sortierte Liste.
Mittel
Multiple Choice #1 20s ▶ Testen

Welche Laufzeit hat ein Algorithmus, der eine sortierte Liste mit binärer Suche durchsucht?

  • ○ O(1)
  • ○ O(n)
  • ● O(log n)
Die binäre Suche halbiert den Suchbereich bei jedem Schritt, daher ist die Laufzeit O(log n) — viel schneller als lineare Suche O(n).
Wahr / Falsch #2 20s ▶ Testen

Ein Algorithmus mit O(n²) ist für große Datenmengen effizienter als einer mit O(n log n).

✓ Falsch
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.
Multiple Choice #3 20s ▶ Testen

Welche Laufzeit hat Bubble Sort im schlimmsten Fall?

  • ○ O(n)
  • ○ O(n log n)
  • ● O(n²)
Bubble Sort vergleicht in jedem Durchlauf benachbarte Elemente. Im schlimmsten Fall (umgekehrt sortierte Liste) benÜtigt er n¡(n-1)/2 Vergleiche = O(n²).
Multiple Choice #4 20s ▶ Testen

Welcher Sortieralgorithmus hat eine durchschnittliche Laufzeit von O(n log n)?

  • ○ Bubble Sort
  • ○ Selection Sort
  • ● Merge Sort
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.
Multiple Choice #5 15s ▶ Testen

Die lineare Suche sucht die Zahl 7. In welcher Liste ist das ihr Best Case?

  • ● 7, 3, 9, 1
  • ○ 3, 9, 1, 7
  • ○ 3, 7, 9, 1
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.
Lückentext #6 15s ▶ Testen

Ein Algorithmus, der die Liste bei jedem Schritt halbiert, hat typischerweise eine Laufzeit von O(___).

✓ Antwort: log n
Halbierung bei jedem Schritt ergibt logarithmisches Wachstum: log₂(1024) = 10, d. h. nur 10 Schritte für 1024 Elemente.
Multiple Choice #7 20s ▶ Testen

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?

  • ● etwa 1.000.000 Sekunden — Ăźber 11 Tage
  • ○ etwa 1.000 Sekunden — knapp 17 Minuten
  • ○ etwa 1 Sekunde — die Datenmenge ändert kaum etwas
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.
Multiple Choice #8 20s ▶ Testen

Ein Algorithmus mit Laufzeit O(2ⁿ) braucht fßr n = 10 rund 1.000 Schritte. Wie viele Schritte braucht er fßr n = 20?

  • ● rund 1.000.000
  • ○ rund 2.000
  • ○ rund 4.000
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.
Wahr / Falsch #9 15s ▶ Testen

Quicksort hat im Average Case eine Laufzeit von O(n log n).

✓ Wahr
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²).
Multiple Choice #10 15s ▶ Testen

Merge Sort legt beim Sortieren von n Zahlen eine Hilfsliste mit n Plätzen an. Welche Speicherkomplexität hat er dadurch?

  • ● O(n)
  • ○ O(1)
  • ○ O(n log n)
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.