Algorithmusanalyse

Einleitung

Algorithmusanalyse untersucht, wie viel Rechenzeit, Speicherplatz und andere Ressourcen ein Algorithmus benötigt, um ein Problem zu lösen. Dabei geht es nicht nur darum, ob ein Programm auf einem bestimmten Computer schnell läuft, sondern darum, wie sich sein Aufwand verändert, wenn die Eingabegröße wächst. Die zentrale Frage lautet: Wie skaliert ein Verfahren?

In diesem aiMOOC lernst Du, wie man Laufzeit und Speicherkomplexität beschreibt, was die O-Notation bedeutet, warum der Worst Case, Best Case und Average Case unterschieden werden und wie typische Datenstrukturen und Sortieralgorithmen analysiert werden. Du lernst außerdem, einfache Pseudocode-Beispiele selbst zu untersuchen und Aussagen über ihre Komplexitätsklasse zu begründen.

Die Algorithmusanalyse ist wichtig für die Informatik, weil viele praktische Probleme nicht allein durch schnellere Hardware gelöst werden können. Ein ungünstiger Algorithmus kann bei großen Datenmengen unbrauchbar werden, während ein gut gewählter Algorithmus dasselbe Problem effizient löst. Besonders in Bereichen wie Suchmaschinen, Kryptographie, Datenbanken, Künstliche Intelligenz, Bioinformatik und Netzwerken entscheidet die Wahl des Algorithmus oft über die praktische Machbarkeit.

Lernziele

Nach diesem aiMOOC kannst Du erklären, was Algorithmusanalyse bedeutet, einfache Laufzeitfunktionen bestimmen, die O-Notation, Omega-Notation und Theta-Notation unterscheiden, typische Wachstumsklassen einordnen und einfache Programme auf Schleifen, Rekursion und Speicherbedarf untersuchen. Außerdem kannst Du begründen, warum lineare Suche, binäre Suche, Mergesort, Quicksort oder Hash-Tabellen in verschiedenen Situationen unterschiedlich geeignet sind.

Medien- und OER-Lernraum

Für die Vertiefung kannst Du sichere, schulgeeignete OER-Quellen und Suchräume nutzen. Binde konkrete Medien nur ein, wenn Du die Lizenz und den Dateinamen eindeutig geprüft hast.

Wikimedia Commons: Suche nach frei nutzbaren Diagrammen zu Wachstumsklassen und Komplexität unter Wikimedia Commons: computational complexity.
Wikipedia und OER: Lies ergänzend die Artikel Wikipedia: Algorithmusanalyse, Wikipedia: Landau-Symbole und Wikipedia: Komplexitätstheorie.
Lernvideo: Suche nach deutschsprachigen Erklärvideos über YouTube: Algorithmusanalyse Big O Notation deutsch.
Interaktive Visualisierung: Nutze Visualisierungen zu Sortieralgorithmen, z. B. über VisuAlgo: Sorting, um Laufzeitverhalten praktisch zu beobachten.

Grundlagen der Algorithmusanalyse

Was ist ein Algorithmus?

Ein Algorithmus ist eine eindeutige, endliche Handlungsvorschrift zur Lösung eines Problems. Er erhält eine Eingabe, verarbeitet diese in einzelnen Schritten und liefert eine Ausgabe. Ein Algorithmus muss nicht zwingend in einer konkreten Programmiersprache geschrieben sein. Häufig wird er zunächst als Pseudocode, Struktogramm oder Flussdiagramm dargestellt.

Für die Algorithmusanalyse ist wichtig, welche Operationen der Algorithmus ausführt. Dazu zählen etwa Vergleiche, Zuweisungen, Rechenoperationen, Speicherzugriffe oder Funktionsaufrufe. Nicht jede einzelne Maschinenoperation wird immer exakt gezählt; meistens interessiert das asymptotische Verhalten, also der Aufwand für sehr große Eingaben.

Eingabegröße

Die Eingabegröße wird meist mit n bezeichnet. Sie beschreibt, wie groß die zu verarbeitenden Daten sind. Bei einer Liste kann n die Anzahl der Elemente sein, bei einem Text die Anzahl der Zeichen, bei einem Graphen die Anzahl der Knoten und Kanten.

Die Wahl der Eingabegröße muss zum Problem passen. Bei einem Sortierverfahren ist die Anzahl der Elemente entscheidend. Bei einem Algorithmus für Graphen kann sowohl die Zahl der Knoten als auch die Zahl der Kanten wichtig sein. Deshalb werden Laufzeiten manchmal als Funktionen von mehreren Größen angegeben, etwa O(V + E) für einen Graphen mit V Knoten und E Kanten.

Ressourcen: Zeit und Speicher

Die zwei wichtigsten Ressourcen sind Laufzeit und Speicherplatz. Die Laufzeitanalyse fragt, wie viele Schritte ein Algorithmus ungefähr benötigt. Die Speicheranalyse fragt, wie viel zusätzlicher Speicher gebraucht wird. Ein Algorithmus kann sehr schnell sein, aber viel Speicher benötigen. Umgekehrt kann ein speichersparender Algorithmus langsamer sein.

Ein Beispiel ist das Sortieren: Manche Verfahren sortieren direkt im vorhandenen Array und benötigen nur wenig Zusatzspeicher. Andere Verfahren, wie Mergesort, verwenden zusätzlichen Speicher, können aber eine garantierte Laufzeit von O(n log n) erreichen. Gute Algorithmusanalyse betrachtet daher immer die Anforderungen der jeweiligen Anwendung.

Maschinelles Messen und theoretisches Analysieren

Man kann Algorithmen praktisch messen, indem man Programme ausführt und Zeiten stoppt. Solche Benchmarks sind nützlich, hängen aber von Computer, Programmiersprache, Compiler, Betriebssystem, Eingabedaten und Implementierung ab. Die theoretische Algorithmusanalyse abstrahiert von diesen Einflüssen. Sie beschreibt das Wachstum des Aufwandes in Abhängigkeit von n.

Beide Perspektiven ergänzen sich. Theoretische Analyse erklärt, warum ein Algorithmus bei großen Datenmengen grundsätzlich besser oder schlechter skaliert. Messungen zeigen, wie sich eine konkrete Implementierung in einer konkreten Umgebung verhält.

Asymptotische Notation

Warum asymptotisch analysieren?

Bei kleinen Eingaben können konstante Faktoren und technische Details wichtiger sein als die mathematische Wachstumsklasse. Bei großen Eingaben entscheidet jedoch oft das Wachstum. Ein Algorithmus mit Laufzeit 100n kann für große n besser sein als ein Algorithmus mit Laufzeit n², obwohl 100n zunächst größer wirkt.

Die asymptotische Analyse konzentriert sich deshalb auf den führenden Wachstumsterm und ignoriert konstante Faktoren. Aus 3n² + 5n + 20 wird asymptotisch O(n²), weil n² bei sehr großen n dominiert.

O-Notation

Die O-Notation beschreibt eine asymptotische obere Schranke. Wenn ein Algorithmus O(n²) ist, wächst sein Aufwand höchstens proportional zu n², wenn n groß genug ist. Die O-Notation wird häufig genutzt, um den Worst-Case-Aufwand anzugeben.

Beispiel: Eine doppelte Schleife, bei der beide Schleifen jeweils n-mal laufen, hat häufig O(n²), weil insgesamt ungefähr n · n Operationen ausgeführt werden.

Omega-Notation

Die Omega-Notation beschreibt eine asymptotische untere Schranke. Wenn ein Algorithmus Ω(n) ist, benötigt er für große Eingaben mindestens proportional zu n viele Schritte. Das kann wichtig sein, wenn man zeigen möchte, dass ein Problem nicht schneller gelöst werden kann, weil jede Eingabe mindestens einmal betrachtet werden muss.

Beispiel: Um in einer unsortierten Liste sicher das größte Element zu finden, muss jedes Element betrachtet werden. Deshalb liegt eine untere Schranke bei Ω(n).

Theta-Notation

Die Theta-Notation beschreibt eine asymptotisch enge Schranke. Wenn ein Algorithmus Θ(n log n) ist, wächst sein Aufwand sowohl nach oben als auch nach unten proportional zu n log n. Die Theta-Notation ist besonders aussagekräftig, weil sie das Wachstum genauer charakterisiert als nur eine obere oder untere Schranke.

Beispiel: Mergesort hat im typischen Vergleichsmodell eine Laufzeit von Θ(n log n), weil die Liste wiederholt geteilt und auf jeder Ebene vollständig zusammengeführt wird.

Typische Wachstumsklassen

Wachstumsklassen helfen beim Vergleich von Algorithmen. Von sehr effizient bis sehr teuer findet man häufig konstante, logarithmische, lineare, linearithmische, quadratische, kubische, exponentielle und faktorielle Laufzeiten.

Wachstum	Schreibweise	Typisches Beispiel	Einordnung
konstant	O(1)	Zugriff auf ein Array-Element über einen Index	Sehr effizient, unabhängig von n
logarithmisch	O(log n)	Binäre Suche in sortierter Liste	Sehr gutes Wachstum bei großen Daten
linear	O(n)	Lineare Suche	Aufwand wächst proportional zur Eingabe
linearithmisch	O(n log n)	Mergesort oder durchschnittlicher Quicksort	Sehr wichtig für effizientes Sortieren
quadratisch	O(n²)	einfache doppelte Schleifen, Bubblesort	Für große n oft problematisch
kubisch	O(n³)	manche Matrix- oder Graphverfahren	Nur bei begrenzter Eingabegröße praktikabel
exponentiell	O(2^n)	vollständige Suche über Teilmengen	Wächst sehr schnell
faktoriell	O(n!)	vollständige Prüfung aller Permutationen	Nur für sehr kleine n praktikabel

Fälle der Laufzeitanalyse

Best Case

Der Best Case beschreibt den günstigsten Fall. Bei einer linearen Suche tritt er ein, wenn das gesuchte Element gleich an erster Stelle steht. Dann wird nur ein Vergleich benötigt. Der Best Case kann nützlich sein, darf aber nicht überschätzt werden, weil er oft selten auftritt.

Worst Case

Der Worst Case beschreibt den ungünstigsten Fall. Bei einer linearen Suche ist das gesuchte Element entweder ganz am Ende oder gar nicht vorhanden. Dann müssen alle Elemente betrachtet werden. Der Worst Case ist besonders wichtig, wenn ein System verlässlich funktionieren muss, etwa in sicherheitskritischer Software oder Echtzeitsystemen.

Average Case

Der Average Case beschreibt den durchschnittlichen Aufwand über viele mögliche Eingaben. Dafür braucht man Annahmen über die Verteilung der Eingaben. Diese Annahmen sind entscheidend: Wenn sie nicht zur Wirklichkeit passen, kann die Average-Case-Aussage irreführend sein.

Ein Beispiel ist Quicksort. Im Durchschnitt ist Quicksort sehr effizient und erreicht O(n log n). Im ungünstigen Fall kann Quicksort jedoch O(n²) benötigen, wenn die Pivotwahl sehr schlecht ist.

Amortisierte Analyse

Die amortisierte Analyse betrachtet nicht nur eine einzelne Operation, sondern eine Folge von Operationen. Manche einzelne Operation kann teuer sein, aber über viele Operationen verteilt ergibt sich ein günstiger Durchschnitt.

Ein Beispiel ist ein dynamisches Array. Wenn das Array voll ist, muss es vergrößert und kopiert werden. Diese einzelne Vergrößerung ist teuer. Da sie aber nicht bei jedem Einfügen geschieht, ist das Einfügen amortisiert oft O(1).

Analyse einfacher Programmstrukturen

Einzelne Anweisungen

Eine einfache Zuweisung, ein Vergleich oder eine arithmetische Operation wird in einfachen Modellen häufig als O(1) betrachtet. Das bedeutet nicht, dass jede Operation physikalisch gleich schnell ist. Es bedeutet, dass sie unabhängig von der Eingabegröße als konstanter Schritt gezählt wird.

Einfache Schleifen

Eine Schleife, die n-mal ausgeführt wird und pro Durchlauf konstant viel Arbeit erledigt, hat O(n). Beispiel:

Pseudocode	Analyse
für i von 1 bis n: gib i aus	Die Schleife läuft n-mal, also O(n).

Wenn eine Schleife nur bis log n läuft, etwa weil sich die Problemgröße in jedem Schritt halbiert, entsteht oft O(log n).

Geschachtelte Schleifen

Geschachtelte Schleifen führen oft zu Produkten. Läuft eine äußere Schleife n-mal und eine innere Schleife ebenfalls n-mal, ergibt sich O(n²). Aber nicht jede geschachtelte Schleife ist automatisch quadratisch. Wenn die innere Schleife nur logarithmisch läuft, kann O(n log n) entstehen.

Struktur	Typische Laufzeit	Begründung
eine Schleife bis n	O(n)	n Durchläufe
zwei vollständige geschachtelte Schleifen bis n	O(n²)	n · n Durchläufe
Schleife mit Halbierung	O(log n)	Problemgröße schrumpft exponentiell
Schleife bis n mit innerer Halbierung	O(n log n)	n-mal logarithmische Arbeit

Bedingungen und Verzweigungen

Bei einer Verzweigung betrachtet man die teuerste relevante Alternative. Wenn ein Algorithmus entweder einen O(n)-Zweig oder einen O(n²)-Zweig ausführen kann, ist der Worst Case O(n²). Für den Average Case müsste man wissen, wie häufig welcher Zweig auftritt.

Rekursion

Bei Rekursion ruft sich ein Algorithmus selbst auf. Die Laufzeit wird oft mit einer Rekursionsgleichung beschrieben. Für Mergesort kann man etwa schreiben: T(n) = 2T(n/2) + O(n). Das bedeutet: Es gibt zwei Teilprobleme halber Größe und zusätzlich lineare Arbeit zum Zusammenführen. Daraus folgt Θ(n log n).

Bei rekursiven Algorithmen ist wichtig, wie viele Teilprobleme entstehen, wie groß sie sind und wie teuer die Arbeit außerhalb der rekursiven Aufrufe ist.

Beispiele wichtiger Algorithmen

Lineare Suche

Die lineare Suche betrachtet Elemente nacheinander, bis das gesuchte Element gefunden wird oder die Liste endet. Sie funktioniert auch bei unsortierten Daten. Der Best Case ist O(1), wenn das Element vorne steht. Der Worst Case ist O(n), wenn es hinten steht oder fehlt.

Lineare Suche ist einfach, robust und für kleine Datenmengen ausreichend. Für sehr große sortierte Daten ist sie jedoch meist schlechter als binäre Suche.

Binäre Suche

Die binäre Suche funktioniert nur auf sortierten Daten. In jedem Schritt wird das mittlere Element betrachtet. Danach kann eine Hälfte ausgeschlossen werden. Dadurch halbiert sich der Suchbereich wiederholt.

Die Laufzeit ist O(log n). Bei einer Million Elementen sind nur ungefähr zwanzig Halbierungsschritte nötig. Dafür muss die Datenmenge sortiert sein, und der Zugriff auf das mittlere Element muss effizient möglich sein.

Bubblesort, Insertionsort und Selectionsort

Einfache Sortierverfahren wie Bubblesort, Insertionsort und Selectionsort sind didaktisch wertvoll, weil sie leicht zu verstehen sind. Sie haben im Allgemeinen quadratische Laufzeit. Für große Datenmengen sind sie deshalb meist ungeeignet.

Insertionsort kann bei fast sortierten Daten gut abschneiden. Bubblesort wird in der Praxis selten eingesetzt, eignet sich aber, um Vergleiche und Vertauschungen anschaulich zu verstehen.

Mergesort

Mergesort teilt die Liste wiederholt in zwei Hälften, sortiert die Teile rekursiv und führt sie anschließend zusammen. Die Laufzeit ist Θ(n log n). Mergesort ist stabil, wenn gleiche Elemente ihre ursprüngliche Reihenfolge behalten.

Ein Nachteil ist der zusätzliche Speicherbedarf, weil beim Zusammenführen häufig Hilfsarrays benötigt werden. Dadurch zeigt Mergesort gut, dass Laufzeit und Speicherbedarf gemeinsam betrachtet werden müssen.

Quicksort

Quicksort wählt ein Pivot-Element und teilt die Daten in kleinere und größere Elemente. Anschließend werden die Teilbereiche rekursiv sortiert. Im Durchschnitt ist Quicksort O(n log n), im Worst Case jedoch O(n²). Gute Pivotstrategien reduzieren das Risiko schlechter Aufteilungen.

Quicksort ist in der Praxis sehr verbreitet, weil es bei guter Implementierung schnell ist und häufig wenig Zusatzspeicher benötigt.

Hash-Tabellen

Eine Hash-Tabelle ordnet Schlüssel mithilfe einer Hashfunktion Speicherpositionen zu. Suchen, Einfügen und Löschen sind im Durchschnitt oft O(1). Im Worst Case kann es jedoch zu vielen Kollisionen kommen, sodass Operationen schlechter werden.

Hash-Tabellen zeigen, dass Durchschnittsfall und Worst Case deutlich voneinander abweichen können. Sie zeigen außerdem, dass Datenstruktur und Algorithmus eng zusammengehören.

Grenzen der Effizienz

Polynomial und exponentiell

Algorithmen mit polynomieller Laufzeit wie O(n), O(n²) oder O(n³) gelten häufig als deutlich besser handhabbar als exponentielle Verfahren wie O(2^n). Diese Einteilung ist jedoch nur eine grobe Orientierung. Ein Algorithmus mit O(n³) kann für sehr große n trotzdem unpraktisch sein, während ein exponentieller Algorithmus für kleine n ausreichend sein kann.

Entscheidungsprobleme und Komplexitätstheorie

Die Komplexitätstheorie untersucht, wie schwer Probleme grundsätzlich sind. Dabei geht es nicht nur um einzelne Algorithmen, sondern um Klassen von Problemen. Bekannte Begriffe sind P, NP und NP-Vollständigkeit. Die berühmte Frage P versus NP ist eines der wichtigsten offenen Probleme der theoretischen Informatik.

Für die schulische Algorithmusanalyse genügt meist die Grundidee: Manche Probleme lassen sich mit bekannten Verfahren effizient lösen, bei anderen wächst der Aufwand so stark, dass große Eingaben praktisch kaum vollständig berechenbar sind.

Trade-offs

Ein Trade-off ist ein Zielkonflikt. Ein Algorithmus kann schneller sein, dafür aber mehr Speicher benötigen. Ein anderer kann einfacher zu verstehen sein, aber schlechter skalieren. In realen Projekten spielen außerdem Wartbarkeit, Implementierungsaufwand, Fehlerrisiko, Energieverbrauch und Datenschutz eine Rolle.

Gute Algorithmusanalyse führt daher nicht automatisch zu einer einzigen richtigen Lösung. Sie hilft Dir, eine begründete Entscheidung für einen bestimmten Kontext zu treffen.

Vorgehensweise bei der Analyse

Schritt-für-Schritt-Methode

Eine hilfreiche Methode besteht darin, zuerst die Eingabegröße zu bestimmen, dann die dominierenden Operationen zu erkennen und schließlich das Wachstum zu vereinfachen. Dabei gilt: Der größte Wachstumsterm bestimmt die asymptotische Klasse.

Eingabegröße: Bestimme, wofür n steht.
Grundoperation: Entscheide, welche Operation gezählt wird, etwa Vergleiche oder Schleifendurchläufe.
Kontrollstruktur: Analysiere Schleifen, Verzweigungen und Rekursion.
Dominanter Term: Vereinfache die Laufzeitfunktion auf den stärksten Wachstumsterm.
Begründung: Formuliere nachvollziehbar, warum die gewählte Komplexitätsklasse gilt.

Beispielanalyse

Gegeben sei folgender Pseudocode:

Für jedes Element x in einer Liste mit n Elementen: Prüfe, ob x größer als das bisherige Maximum ist.

Der Algorithmus betrachtet jedes Element genau einmal. Pro Element wird konstant viel Arbeit ausgeführt. Die Laufzeit ist deshalb O(n). Da jedes Element betrachtet werden muss, um sicher das Maximum zu finden, liegt auch Ω(n) vor. Insgesamt ergibt sich Θ(n).

Häufige Fehler

Viele Lernende schließen vorschnell von einer Schleife auf O(n) oder von zwei Schleifen auf O(n²). Entscheidend ist aber, wie oft die Schleife wirklich läuft. Auch Konstanten dürfen in der O-Notation vernachlässigt werden, aber nicht die Struktur des Problems. Ein weiterer Fehler ist, Best Case, Worst Case und Average Case zu vermischen.

Wichtig ist außerdem: Die O-Notation beschreibt Wachstum, nicht konkrete Sekunden. Zwei Algorithmen mit derselben O-Klasse können in der Praxis unterschiedlich schnell sein. Trotzdem bleibt die asymptotische Analyse ein zentrales Werkzeug, weil sie grundlegende Skalierung sichtbar macht.

Interaktive Aufgaben

Quiz: Teste Dein Wissen

Was untersucht die Algorithmusanalyse hauptsächlich? (Den Ressourcenbedarf eines Algorithmus in Abhängigkeit von der Eingabegröße) (!Die Farbe der Benutzeroberfläche eines Programms) (!Die Lizenzbedingungen einer Software) (!Die Reihenfolge der Tasten auf einer Tastatur)

Was bedeutet O(n) typischerweise? (Der Aufwand wächst ungefähr proportional zur Eingabegröße) (!Der Aufwand ist unabhängig von der Eingabegröße) (!Der Aufwand verdoppelt sich immer nach exakt einer Sekunde) (!Der Algorithmus kann nur Zahlen verarbeiten)

Welche Laufzeit hat die binäre Suche in einer sortierten Liste typischerweise? (O log n) (!O n) (!O n Quadrat) (!O zwei hoch n)

Was beschreibt der Worst Case? (Den ungünstigsten möglichen Fall für eine Eingabe) (!Den durchschnittlichen Fall über alle möglichen Computer) (!Den schnellsten möglichen Ablauf) (!Die schönste Implementierung eines Algorithmus)

Welche Aussage zur Theta-Notation ist richtig? (Sie beschreibt eine asymptotisch enge Schranke) (!Sie beschreibt nur eine grafische Darstellung) (!Sie bedeutet immer konstante Laufzeit) (!Sie gilt nur für Sortieralgorithmen)

Welche Datenstruktur ermöglicht Suchen im Durchschnitt oft in O eins? (Hash-Tabelle) (!Unsortierte Papierliste) (!Lineare Kette ohne Index) (!Zufällig gemischter Text)

Warum kann eine doppelte vollständige Schleife häufig O n Quadrat haben? (Weil n Durchläufe mit n weiteren Durchläufen kombiniert werden) (!Weil jeder Algorithmus mit zwei Zeilen quadratisch ist) (!Weil Computer nur Quadratzahlen speichern) (!Weil die Eingabe immer sortiert sein muss)

Welche Laufzeitklasse wächst bei großen Eingaben meist schneller als quadratisch? (Exponentiell) (!Linear) (!Konstant) (!Logarithmisch)

Was ist eine amortisierte Analyse? (Die Betrachtung der durchschnittlichen Kosten über eine Folge von Operationen) (!Die Analyse der Bildschirmgröße) (!Die Übersetzung eines Programms in eine andere Sprache) (!Die Speicherung aller Daten in alphabetischer Reihenfolge)

Welche Aussage zu Benchmarks ist richtig? (Sie messen konkrete Implementierungen unter bestimmten Bedingungen) (!Sie ersetzen jede theoretische Analyse vollständig) (!Sie sind unabhängig von Hardware und Programmiersprache) (!Sie liefern immer dieselben Ergebnisse auf jedem Computer)

Memory

O eins	Konstanter Zugriff
O log n	Binäre Suche
O n	Lineare Suche
O n log n	Mergesort
O n Quadrat	Doppelte Schleife
Worst Case	Ungünstigster Fall
Average Case	Durchschnittlicher Fall

Drag and Drop

Ordne die richtigen Begriffe zu.	Thema
Konstante Laufzeit	Zugriff auf ein Array-Element
Logarithmische Laufzeit	Halbierung des Suchraums
Lineare Laufzeit	Einmaliges Durchlaufen einer Liste
Quadratische Laufzeit	Vollständig geschachtelte Schleifen
Exponentielle Laufzeit	Vollständige Suche über Teilmengen

Kreuzworträtsel

Laufzeit	Welche Ressource beschreibt die benötigte Zeit eines Algorithmus?
Speicher	Welche Ressource beschreibt den zusätzlichen Platzbedarf?
Quicksort	Welcher Sortieralgorithmus nutzt typischerweise ein Pivot-Element?
Mergesort	Welcher Sortieralgorithmus teilt und führt sortierte Teile zusammen?
Hashing	Welches Prinzip ordnet Schlüssel Speicherpositionen zu?
Rekursion	Wie nennt man es, wenn sich ein Algorithmus selbst aufruft?

LearningApps

Lückentext

Die Algorithmusanalyse untersucht den

eines Algorithmus in Abhängigkeit von der Eingabegröße. Die Eingabegröße wird häufig mit

bezeichnet. Die O-Notation beschreibt eine asymptotische

Schranke. Die Omega-Notation beschreibt eine asymptotische

Schranke. Eine enge Schranke wird mit der

beschrieben. Bei der binären Suche wird der Suchbereich in jedem Schritt ungefähr

. Eine lineare Suche benötigt im Worst Case

Schritte. Mergesort hat typischerweise die Laufzeit

. Bei einer Hash-Tabelle sind Suchoperationen im Durchschnitt oft

. Die amortisierte Analyse betrachtet die Kosten über eine

von Operationen.

Offene Aufgaben

Leicht

Begriffe erklären: Erstelle ein Mini-Glossar mit zehn Begriffen zur Algorithmusanalyse, darunter Laufzeit, Speicherkomplexität, O-Notation, Worst Case und Eingabegröße.
Alltagsalgorithmus: Beschreibe einen Alltagsalgorithmus, etwa das Suchen eines Buches im Regal, und erkläre, welche Eingabegröße dabei eine Rolle spielt.
Wachstum vergleichen: Zeichne per Hand ein Koordinatensystem und skizziere grob die Wachstumsklassen O(1), O(log n), O(n), O(n²) und O(2^n).
Suchverfahren vergleichen: Vergleiche lineare Suche und binäre Suche an einer sortierten Liste mit 16 Elementen und notiere die benötigten Schritte.

Standard

Pseudocode analysieren: Schreibe einen Pseudocode mit einer einfachen Schleife und bestimme seine Laufzeitklasse.
Schleifen untersuchen: Analysiere drei verschiedene Schleifenstrukturen und erkläre, warum sie O(n), O(log n) oder O(n²) haben.
Sortierverfahren beobachten: Nutze eine Visualisierung zu Sortieralgorithmen und beschreibe, wie sich Bubblesort, Mergesort und Quicksort bei wachsenden Listen unterscheiden.
Benchmark kritisch prüfen: Führe einen kleinen Laufzeitvergleich zweier Suchverfahren durch und erkläre, warum Messwerte allein keine vollständige Algorithmusanalyse ersetzen.

Schwer

Rekursion analysieren: Erstelle eine Rekursionsgleichung für einen rekursiven Algorithmus und löse sie mit einer begründeten Abschätzung.
Trade-off bewerten: Vergleiche zwei Lösungen für dasselbe Problem, bei denen eine schneller ist und die andere weniger Speicher benötigt. Begründe, wann welche Lösung sinnvoller ist.
Komplexität im Alltag: Recherchiere ein reales Problem aus Datenbanken, Künstliche Intelligenz oder Kryptographie und erkläre, warum effiziente Algorithmen dort entscheidend sind.
Algorithmus verbessern: Entwickle für ein einfaches Problem zunächst eine naive Lösung und anschließend eine effizientere Lösung. Vergleiche beide mit O-Notation und einem Beispiel.

type=create break=no preload=CHAT GPT TEXT HIER EINFÜGEN default= width=30 placeholder= Dein MOOC Titel buttonlabel=MOOC erstellen </inputbox>

Lernkontrolle

Transfer auf neue Probleme: Du erhältst einen unbekannten Pseudocode mit mehreren Schleifen. Bestimme nicht nur die Laufzeitklasse, sondern erkläre genau, welche Programmstruktur den dominierenden Aufwand verursacht.
Begründete Entscheidung: Eine unsortierte Liste soll häufig durchsucht werden. Begründe, ob Sortieren mit anschließender binärer Suche sinnvoll ist oder ob lineare Suche ausreicht.
Fallunterscheidung: Erkläre an einem selbst gewählten Beispiel, warum Best Case, Average Case und Worst Case zu unterschiedlichen Aussagen führen können.
Ressourcenkonflikt: Beurteile eine Situation, in der ein schneller Algorithmus sehr viel Speicher benötigt. Entwickle Kriterien, nach denen Du eine Entscheidung triffst.
Skalierung einschätzen: Vergleiche zwei Algorithmen mit O(n²) und O(n log n) für kleine und große Eingaben. Erkläre, warum die bessere Wahl von der Eingabegröße abhängen kann.
Grenzen erkennen: Beschreibe, warum exponentielle Verfahren bei großen Eingaben schnell unpraktisch werden und nenne eine Strategie, mit der man trotzdem Näherungslösungen finden könnte.

Lernnachweis

Der Lernnachweis zu diesem aiMOOC prüft, ob Du Zusammenhänge erklären, neue Beispiele analysieren und begründete Entscheidungen treffen kannst. Bearbeite die Aufgaben schriftlich oder in einer Präsentation. Nutze keine externen Medien im Lernnachweis, sondern eigene Begründungen, Skizzen und Pseudocode.

Analyseaufgabe: Erkläre an einem selbst gewählten Pseudocode mit mindestens zwei Kontrollstrukturen, welche Laufzeitklasse entsteht und warum.
Vergleichsaufgabe: Vergleiche zwei Algorithmen für dasselbe Problem hinsichtlich Laufzeit, Speicherbedarf und Verständlichkeit.
Transferaufgabe: Entwickle zu einem Alltagsproblem zwei Lösungswege und beschreibe, welcher bei wachsender Eingabegröße besser skaliert.
Argumentationsaufgabe: Begründe, warum eine schlechtere asymptotische Laufzeit bei sehr kleinen Eingaben trotzdem praktisch akzeptabel sein kann.
Reflexionsaufgabe: Beschreibe, welche Grenzen die O-Notation hat und warum Messungen in der Praxis trotzdem hilfreich sein können.

OERs zum Thema

Weitere freie Lern- und Recherchequellen:

Wikipedia: Landau-Symbole zur mathematischen Notation asymptotischer Schranken.
Wikimedia Commons: Medienrecherche zu algorithm analysis.
OER-Suche: OERinfo-Suche zu Algorithmusanalyse.
Lernvideo-Suche: YouTube-Suche zu Laufzeit und O-Notation.

Links

Algorithmusanalyse

Zusammenfassung

Die Algorithmusanalyse ist ein grundlegendes Werkzeug der Informatik. Sie hilft Dir zu beurteilen, wie gut ein Algorithmus mit wachsender Eingabegröße skaliert. Mit O-Notation, Omega-Notation und Theta-Notation beschreibst Du asymptotische Schranken. Durch die Unterscheidung von Best Case, Worst Case und Average Case erkennst Du, dass der Aufwand stark von den Eingabedaten abhängen kann. Die Analyse von Schleifen, Verzweigungen und Rekursion bildet die Grundlage, um Pseudocode und Programme systematisch zu bewerten. In der Praxis ist die beste Lösung nicht immer nur die schnellste, sondern diejenige, die Laufzeit, Speicherbedarf, Verständlichkeit und Anwendungskontext sinnvoll ausbalanciert.

aiMOOC-Projekte

Schulfach+

Prüfungsliteratur 2026
Bundesland	Bücher	Kurzbeschreibung
Baden-Württemberg	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck Mittlere Reife Der Markisenmann - Jan Weiler oder Als die Welt uns gehörte - Liz Kessler Ein Schatten wie ein Leopard - Myron Levoy oder Pampa Blues - Rolf Lappert	Abitur Dorfrichter-Komödie über Wahrheit/Schuld; Roman über einen Ort und deutsche Geschichte. Mittlere Reife Wahllektüren (Roadtrip-Vater-Sohn / Jugendroman im NS-Kontext / Coming-of-age / Provinzroman).
Bayern	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Lustspiel über Machtmissbrauch und Recht; Roman als Zeitschnitt deutscher Geschichte an einem Haus/Grundstück.
Berlin/Brandenburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Der Biberpelz - Gerhart Hauptmann Heimsuchung - Jenny Erpenbeck	Abitur Gerichtskomödie; soziales Drama um Ausbeutung/Armut; Komödie/Satire um Diebstahl und Obrigkeit; Roman über Erinnerungsräume und Umbrüche.
Bremen	Abitur Nach Mitternacht - Irmgard Keun Mario und der Zauberer - Thomas Mann Emilia Galotti - Gotthold Ephraim Lessing oder Miss Sara Sampson - Gotthold Ephraim Lessing	Abitur Roman in der NS-Zeit (Alltag, Anpassung, Angst); Novelle über Verführung/Massenpsychologie; bürgerliche Trauerspiele (Moral, Macht, Stand).
Hamburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun	Abitur Justiz-/Machtkritik als Komödie; Großstadtroman der Weimarer Zeit (Rollenbilder, Aufstiegsträume, soziale Realität).
Hessen	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Heimsuchung - Jenny Erpenbeck Der Prozess - Franz Kafka	Abitur Gerichtskomödie; Fragmentdrama über Gewalt/Entmenschlichung; Erinnerungsroman über deutsche Brüche; moderner Roman über Schuld, Macht und Bürokratie.
Niedersachsen	Abitur Der zerbrochene Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun Die Marquise von O. - Heinrich von Kleist Über das Marionettentheater - Heinrich von Kleist	Abitur Schwerpunkt auf Drama/Roman sowie Kleist-Prosatext und Essay (Ehre, Gewalt, Unschuld; Ästhetik/„Anmut“).
Nordrhein-Westfalen	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Komödie über Wahrheit und Autorität; Roman als literarische „Geschichtsschichtung“ an einem Ort.
Saarland	Abitur Heimsuchung - Jenny Erpenbeck Furor - Lutz Hübner und Sarah Nemitz Bahnwärter Thiel - Gerhart Hauptmann	Abitur Erinnerungsroman an einem Ort; zeitgenössisches Drama über Eskalation/Populismus; naturalistische Novelle (Pflicht/Überforderung/Abgrund).
Sachsen (berufliches Gymnasium)	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Irrungen, Wirrungen - Theodor Fontane Der gute Mensch von Sezuan - Bertolt Brecht Heimsuchung - Jenny Erpenbeck Der Trafikant - Robert Seethaler	Abitur Mischung aus Klassiker-Drama, sozialem Drama, realistischem Roman, epischem Theater und Gegenwarts-/Erinnerungsroman; zusätzlich Coming-of-age im historischen Kontext.
Sachsen-Anhalt	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Themenfelder)	Abitur Schwerpunktsetzung über Themenfelder (u. a. Literatur um 1900; Sprache in politisch-gesellschaftlichen Kontexten), ohne feste Einzeltitel.
Schleswig-Holstein	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Recht/Gerechtigkeit und historische Tiefenschichten eines Ortes – umgesetzt über Drama und Gegenwartsroman.
Thüringen	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Orientierung am gemeinsamen Aufgabenpool)	Abitur In der Praxis häufig Orientierung am gemeinsamen Aufgabenpool; landesweite Einzeltitel je nach Vorgabe/Handreichung nicht einheitlich ausgewiesen.
Mecklenburg-Vorpommern	Abitur (Quelle aktuell technisch nicht abrufbar; Beteiligung am gemeinsamen Aufgabenpool bekannt)	Abitur Land beteiligt sich am länderübergreifenden Aufgabenpool; konkrete, veröffentlichte Einzeltitel konnten hier nicht ausgelesen werden.
Rheinland-Pfalz	Abitur (keine landesweit einheitliche Pflichtlektüre; schulische Auswahl)	Abitur Keine landesweite Einheitsliste; Auswahl kann schul-/kursbezogen erfolgen.