Algorithmuseffizienz: Laufzeit und Speicherbedarf

Konzepte der Informatik

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Einführung in die Big-O-Notation

Misst Wachstum von Zeit und Speicher mit wachsendem Input
Beispiele: $O(n)$, $O(n^2)$, $O(log\, n)$
„O“ steht für die Wachstumsordnung, z. B. O(n) = linear

Zeitkomplexität – Büro-Analogie

Ein Diagramm mit verschiedenen Big-O-Komplexitäten

$O(1)$ – konstante Zeit – „schneller Blick“ – „konstant“
$O(log\,n)$ – langsamer Anstieg – „stapeln & teilen“ – „logarithmisch“
$O(n)$ – linearer Anstieg – „Dokument lesen“ – „linear“
$O(n\,log\,n)$ – schnellerer Anstieg – „Stapel sortieren“ – „linearithmisch“
$O(n^2)$ – quadratischer Anstieg – „Dokumente vergleichen“ – „quadratisch“

Speicherkomplexität – Büro-Analogie

Ein Diagramm mit verschiedenen Big-O-Komplexitäten

$O(1)$ – konstanter Speicher – „Schreibtischfläche“ – „konstant“
$O(log\,n)$ – langsamer Anstieg – „Mininotizen“ – „logarithmisch“
$O(n)$ – linearer Anstieg – „Haftnotizen“ – „linear“
$O(n\,log\,n)$ – schnellerer Anstieg – „temporäre Stapel“ – „linearithmisch“
$O(n^2)$ – quadratischer Anstieg – „Vergleichsraster“ – „quadratisch“

Lass uns üben!

Konzepte der Informatik

Preparing Video For Download...