Algorithmenanalyse

Algorithmenanalyse untersucht, wie viele Ressourcen ein Algorithmus zur Lösung eines Problems benötigt. Besonders wichtig sind die Laufzeit und der Speicherbedarf. Dabei geht es nicht nur darum, ein Programm einmal auf einem bestimmten Computer zu messen, sondern sein Verhalten systematisch zu beschreiben: Wie verändert sich der Aufwand, wenn die Eingabe größer wird? Diese Frage ist zentral für Informatik, Mathematik, Programmierung, Datenstrukturen und viele technische Anwendungen.

Ein Algorithmus kann für kleine Eingaben schnell wirken und bei großen Eingaben trotzdem unbrauchbar werden. Die Algorithmenanalyse hilft Dir, solche Unterschiede zu erkennen. Sie verwendet unter anderem Landau-Symbole wie O, Ω und Θ, um Wachstumsraten zu vergleichen. Dadurch kannst Du einschätzen, ob ein Verfahren bei großen Datenmengen noch praktikabel ist.

Lernziele

Nach diesem aiMOOC kannst Du erklären, was Laufzeitanalyse und Speicherkomplexität bedeuten. Du kannst typische Wachstumsordnungen wie konstante, logarithmische, lineare, quadratische und exponentielle Laufzeit unterscheiden. Außerdem kannst Du einfache Algorithmen analysieren, Schleifen und Rekursion untersuchen, Best Case, Average Case und Worst Case unterscheiden und begründet entscheiden, welcher Algorithmus für eine konkrete Situation geeignet ist.

Medien- und OER-Lernraum

Nutze die folgenden schulgeeigneten OER-Hinweise, um Dir zusätzliche Erklärungen, Abbildungen und Lernvideos zu erschließen. Sie sind als Recherche- und Vertiefungsangebote gedacht, damit keine unsicheren Datei- oder Videoangaben eingebunden werden.

Grundlagen

Was ist ein Algorithmus?

Ein Algorithmus ist eine endliche, eindeutig beschriebene Folge von Schritten, die ein Problem löst oder eine Aufgabe bearbeitet. Ein Algorithmus kann in natürlicher Sprache, als Pseudocode, als Programmcode, als Flussdiagramm oder mathematisch beschrieben werden. Für die Algorithmenanalyse ist wichtig, dass die einzelnen Schritte klar genug sind, um ihren Aufwand abzuschätzen.

Beispiel: Wenn Du in einer unsortierten Liste nach einem Namen suchst, kannst Du die Liste von vorne nach hinten durchgehen. Im schlimmsten Fall steht der Name ganz am Ende oder gar nicht in der Liste. Dann musst Du jedes Element prüfen. Bei einer Liste mit n Elementen wächst der Aufwand ungefähr proportional zu n. Man spricht von linearer Suche und linearer Laufzeit.

Warum analysiert man Algorithmen?

Die Analyse von Algorithmen ist notwendig, weil reale Programme mit unterschiedlich großen Datenmengen arbeiten. Eine App, ein Suchsystem, eine Simulation oder ein Datenbankprogramm kann bei 100 Einträgen problemlos funktionieren, aber bei 100 Millionen Einträgen scheitern. Durch Algorithmenanalyse kannst Du bereits vor der Implementierung abschätzen, ob ein Lösungsweg grundsätzlich geeignet ist.

Die Analyse hilft besonders bei folgenden Entscheidungen: Welche Datenstruktur ist sinnvoll? Welches Sortierverfahren passt zur Datenlage? Lohnt sich eine Vorverarbeitung? Muss Speicher gespart werden? Ist eine exakte Lösung möglich oder braucht man eine Heuristik?

Eingabegröße n

Die Eingabegröße wird häufig mit n bezeichnet. Was n genau bedeutet, hängt vom Problem ab. Bei einer Liste ist n meist die Anzahl der Elemente. Bei einer Zeichenkette ist n oft die Länge der Zeichenkette. Bei einem Graph können die Anzahl der Knoten und die Anzahl der Kanten getrennt betrachtet werden. Bei einer Matrix können Zeilen und Spalten eine Rolle spielen.

Eine gute Analyse beginnt deshalb mit der Frage: Was ist die relevante Eingabegröße? Erst danach lässt sich sinnvoll bestimmen, wie sich der Aufwand bei wachsenden Eingaben verändert.

Rechenmodell

Ein Rechenmodell legt fest, welche Operationen als elementare Schritte gezählt werden. In einfachen Schul- und Einstiegssituationen nimmt man oft an, dass Vergleiche, Zuweisungen, arithmetische Grundoperationen und Speicherzugriffe jeweils konstant viel Zeit benötigen. Diese Annahme ist eine Vereinfachung, macht aber viele Analysen übersichtlich.

In der Praxis können Hardware, Programmiersprache, Compiler, Cache, Betriebssystem und Netzwerkzugriffe die tatsächliche Laufzeit beeinflussen. Die Algorithmenanalyse abstrahiert von diesen Details, damit grundlegende Wachstumsunterschiede sichtbar werden.

Laufzeitanalyse

Zählen von Operationen

Bei der Laufzeitanalyse wird abgeschätzt, wie viele elementare Operationen ein Algorithmus ausführt. Entscheidend ist meistens nicht die exakte Zahl aller Maschinenbefehle, sondern die Wachstumsordnung. Ob ein Algorithmus ungefähr 3n, 7n oder 20n Schritte benötigt, ist für sehr große n oft weniger wichtig als der Unterschied zwischen n, n² und 2ⁿ.

Ein einfaches Beispiel:

summe = 0
für jedes element in liste:
    summe = summe + element

Wenn die Liste n Elemente enthält, wird die Schleife n-mal durchlaufen. Der Aufwand wächst linear mit n. Die Laufzeit gehört deshalb zur Ordnung O(n).

Schleifen analysieren

Schleifen sind ein häufiger Ausgangspunkt der Analyse. Eine einfache Schleife, die n-mal läuft, deutet oft auf lineare Laufzeit hin. Zwei verschachtelte Schleifen, die jeweils n-mal laufen, deuten oft auf quadratische Laufzeit hin. Dabei muss man genau prüfen, ob die innere Schleife wirklich immer vollständig läuft.

Beispiel für quadratische Laufzeit:

für i von 1 bis n:
    für j von 1 bis n:
        vergleiche element i mit element j

Hier werden ungefähr n · n Vergleiche durchgeführt. Der Aufwand wächst quadratisch und wird als O(n²) beschrieben.

Rekursion analysieren

Bei Rekursion ruft sich ein Algorithmus selbst mit kleineren Teilproblemen auf. Die Analyse erfolgt häufig mit einer Rekursionsgleichung. Dabei wird beschrieben, wie sich der Aufwand eines Problems der Größe n aus den Aufwänden kleinerer Teilprobleme zusammensetzt.

Beispiel: Ein Verfahren halbiert das Problem bei jedem Schritt und führt zusätzlich konstanten Aufwand aus. Dann ergibt sich häufig eine logarithmische Laufzeit. Wenn ein Verfahren dagegen zwei Teilprobleme der halben Größe bearbeitet und zusätzlich linearen Aufwand benötigt, entsteht oft eine Laufzeit der Ordnung O(n log n).

Best Case, Average Case und Worst Case

Der Best Case beschreibt den günstigsten Fall. Der Worst Case beschreibt den ungünstigsten Fall. Der Average Case beschreibt das erwartete Verhalten über viele typische Eingaben hinweg. Diese drei Perspektiven können stark voneinander abweichen.

Bei der linearen Suche ist der Best Case erreicht, wenn das gesuchte Element direkt am Anfang steht. Dann reicht ein Vergleich. Im Worst Case steht das Element am Ende oder fehlt ganz. Dann müssen alle n Elemente geprüft werden. Im Average Case liegt der Treffer bei zufälliger Verteilung ungefähr in der Mitte, dennoch bleibt die Wachstumsordnung linear.

Amortisierte Analyse

Die amortisierte Analyse betrachtet nicht nur eine einzelne Operation, sondern eine Folge von Operationen. Eine einzelne Operation kann teuer sein, während die durchschnittlichen Kosten über viele Operationen hinweg niedrig bleiben. Ein typisches Beispiel ist eine dynamische Liste, die gelegentlich vergrößert werden muss. Das Kopieren aller Elemente ist teuer, passiert aber selten. Über viele Einfügeoperationen betrachtet bleiben die Kosten pro Einfügen oft konstant im amortisierten Sinn.

Asymptotische Analyse

Idee der Asymptotik

Die Asymptotik betrachtet das Verhalten für sehr große Eingaben. Kleine Unterschiede und konstante Faktoren werden dabei häufig ausgeblendet. Das Ziel ist nicht, eine Stoppuhrmessung zu ersetzen, sondern die langfristige Entwicklung des Aufwands zu verstehen.

Wenn ein Algorithmus 100n Schritte benötigt und ein anderer n² Schritte, kann der quadratische Algorithmus bei kleinen n schneller sein. Bei großen n wächst n² jedoch deutlich stärker. Die asymptotische Analyse macht solche Wachstumsunterschiede sichtbar.

Landau-Symbole

Landau-Symbole beschreiben obere, untere und enge Schranken für das Wachstum von Funktionen.

Symbol	Bedeutung	Typische Aussage
O	obere Schranke	Der Aufwand wächst höchstens in dieser Ordnung.
Ω	untere Schranke	Der Aufwand wächst mindestens in dieser Ordnung.
Θ	enge Schranke	Der Aufwand wächst genau in dieser Ordnung bis auf konstante Faktoren.

Wenn ein Algorithmus die Laufzeit Θ(n) hat, bedeutet das: Sein Aufwand wächst linear und lässt sich sowohl nach oben als auch nach unten durch lineare Funktionen begrenzen.

Typische Wachstumsordnungen

Ordnung	Name	Beispielhafte Bedeutung
O(1)	konstant	Der Aufwand bleibt unabhängig von n ungefähr gleich.
O(log n)	logarithmisch	Das Problem wird wiederholt verkleinert, zum Beispiel halbiert.
O(n)	linear	Jedes Element wird einmal betrachtet.
O(n log n)	linearithmisch	Typisch für effiziente vergleichsbasierte Sortierverfahren.
O(n²)	quadratisch	Häufig bei zwei verschachtelten Schleifen über dieselbe Datenmenge.
O(2ⁿ)	exponentiell	Der Aufwand verdoppelt sich ungefähr mit jedem zusätzlichen Eingabeelement.
O(n!)	faktoriell	Alle möglichen Anordnungen werden ausprobiert.

Die Reihenfolge zeigt, dass kleine Unterschiede in der Wachstumsordnung große praktische Folgen haben können. Besonders exponentielle und faktorielle Verfahren werden schon bei moderaten Eingabegrößen sehr schnell unpraktisch.

Konstante Faktoren und niedrigere Terme

In der asymptotischen Analyse werden konstante Faktoren und niedrigere Terme oft vernachlässigt. Aus 5n² + 20n + 100 wird asymptotisch O(n²). Der quadratische Term dominiert für große n. Trotzdem können konstante Faktoren in der Praxis wichtig sein, vor allem bei kleinen oder mittleren Eingaben. Deshalb ergänzen sich theoretische Analyse und praktische Messung.

Speicherkomplexität

Speicherbedarf eines Algorithmus

Die Speicherkomplexität beschreibt, wie viel zusätzlicher Speicher ein Algorithmus benötigt. Man unterscheidet häufig zwischen dem Speicher für die Eingabe und zusätzlichem Hilfsspeicher. Ein Algorithmus kann schnell sein, aber viel Speicher verbrauchen. Ein anderer Algorithmus kann sparsamer mit Speicher umgehen, dafür aber länger laufen.

Beispiel: Ein Sortierverfahren, das eine zusätzliche Liste gleicher Größe anlegt, benötigt zusätzlichen Speicher der Ordnung O(n). Ein Verfahren, das überwiegend innerhalb der vorhandenen Liste arbeitet, kann mit konstantem Zusatzspeicher auskommen.

Zeit-Speicher-Abwägung

In vielen Situationen gibt es einen Zeit-Speicher-Trade-off. Zusätzlicher Speicher kann Laufzeit sparen, etwa durch Hash-Tabellen, Zwischenspeicherung oder Vorberechnung. Umgekehrt kann Speicher gespart werden, wenn man mehr Rechenzeit akzeptiert.

Ein Beispiel ist die Suche nach häufig abgefragten Daten. Werden Ergebnisse in einem Cache gespeichert, können spätere Anfragen schneller beantwortet werden. Dafür wird zusätzlicher Speicher benötigt.

Beispiele der Algorithmenanalyse

Lineare Suche

Bei der linearen Suche wird eine Liste Element für Element durchsucht. Für eine unsortierte Liste ist das ein naheliegendes Verfahren. Im Worst Case müssen alle Elemente betrachtet werden.

Eigenschaft	Analyse
Eingabe	unsortierte Liste mit n Elementen
Best Case	Treffer beim ersten Element
Worst Case	Treffer am Ende oder kein Treffer
Laufzeit	O(n)
Zusatzspeicher	O(1)

Binäre Suche

Die binäre Suche funktioniert nur auf sortierten Daten. Bei jedem Schritt wird der Suchbereich halbiert. Dadurch entsteht logarithmische Laufzeit.

Eigenschaft	Analyse
Voraussetzung	sortierte Liste
Idee	wiederholtes Halbieren des Suchbereichs
Laufzeit	O(log n)
Zusatzspeicher	iterativ meist O(1)

Die binäre Suche zeigt, warum Vorbedingungen wichtig sind. Das Sortieren einer Liste kostet zunächst Aufwand. Wenn danach aber sehr viele Suchanfragen gestellt werden, kann sich diese Vorarbeit lohnen.

Sortierverfahren

Sortierverfahren eignen sich besonders gut, um Algorithmenanalyse zu üben. Einfache Verfahren wie Bubble Sort, Selection Sort oder Insertion Sort sind leicht zu verstehen, haben aber oft quadratische Laufzeit. Effizientere Verfahren wie Merge Sort oder Quicksort erreichen im Durchschnitt oder im garantierten Fall häufig bessere Wachstumsordnungen.

Verfahren	Typische Laufzeit	Bemerkung
Bubble Sort	O(n²)	didaktisch einfach, praktisch meist langsam
Insertion Sort	O(n²)	für fast sortierte kleine Daten oft brauchbar
Merge Sort	O(n log n)	stabil, benötigt meist zusätzlichen Speicher
Quicksort	durchschnittlich O(n log n)	sehr schnell in der Praxis, Worst Case O(n²)

Graphalgorithmen

Bei Graphalgorithmen hängt die Analyse häufig von zwei Größen ab: der Anzahl der Knoten und der Anzahl der Kanten. Eine Breitensuche oder Tiefensuche kann in der Ordnung O(V + E) analysiert werden, wenn V für die Knoten und E für die Kanten steht. Dadurch wird sichtbar, dass nicht nur die Anzahl der Objekte, sondern auch ihre Verbindungen entscheidend sind.

Vorgehensweise bei einer Analyse

Eine systematische Algorithmenanalyse kann in mehreren Schritten erfolgen:

Problemverständnis: Kläre, welches Problem gelöst wird und welche Eingaben möglich sind.
Eingabegröße: Bestimme, was n oder andere Größen wie V und E bedeuten.
Grundoperation: Lege fest, welche Operation gezählt wird, zum Beispiel Vergleiche oder Zuweisungen.
Kontrollstruktur: Untersuche Schleifen, Verzweigungen und Rekursion.
Fallunterscheidung: Betrachte Best Case, Average Case und Worst Case.
Asymptotik: Vereinfache die Wachstumsfunktion mit Landau-Symbolen.
Interpretation: Erkläre, was die Analyse praktisch bedeutet.

Häufige Fehler

Ein häufiger Fehler ist die Gleichsetzung von praktischer Messzeit und theoretischer Komplexität. Eine Messung kann durch Hardware oder Implementierungsdetails beeinflusst sein. Die Komplexität beschreibt dagegen eine abstrakte Wachstumsordnung.

Ein weiterer Fehler ist die falsche Analyse verschachtelter Schleifen. Nicht jede Verschachtelung führt automatisch zu O(n²). Wenn sich die innere Schleife zum Beispiel halbiert oder nur insgesamt n Schritte über alle äußeren Durchläufe ausführt, kann eine andere Ordnung entstehen.

Auch die Eingabegröße wird oft unklar gewählt. Bei Graphen reicht es nicht immer, nur von n zu sprechen. Man muss angeben, ob Knoten, Kanten oder beide Größen gemeint sind.

Bedeutung in Schule, Studium und Praxis

In der Schule hilft Dir die Algorithmenanalyse, Programme nicht nur zum Laufen zu bringen, sondern ihre Qualität zu beurteilen. Im Studium bildet sie eine Grundlage für Datenstrukturen, Komplexitätstheorie, Software Engineering, Künstliche Intelligenz und Datenbanken. In der Praxis entscheidet sie mit darüber, ob Suchmaschinen, Routenplaner, Empfehlungssysteme, Simulationen oder Sicherheitsverfahren effizient funktionieren.

Algorithmenanalyse ist deshalb mehr als Rechnen mit Formeln. Sie ist eine Denkweise: Du untersuchst, wie ein Lösungsweg wächst, wo Engpässe entstehen und welche Alternative unter welchen Bedingungen sinnvoll ist.

Interaktive Aufgaben

Quiz: Teste Dein Wissen

Was untersucht die Algorithmenanalyse hauptsächlich? (Den Ressourcenbedarf von Algorithmen) (!Die Farbe einer Benutzeroberfläche) (!Die Rechtschreibung von Programmkommentaren) (!Die Lautstärke eines Computers)

Was beschreibt die Eingabegröße n typischerweise? (Die Größe der zu verarbeitenden Eingabe) (!Die Versionsnummer eines Programms) (!Die Anzahl der Programmiersprachen) (!Die Taktfrequenz des Monitors)

Welche Laufzeit entsteht häufig bei einer einfachen Schleife über alle Listenelemente? (Lineare Laufzeit) (!Faktorielle Laufzeit) (!Konstante Laufzeit) (!Exponentielle Laufzeit)

Welche Voraussetzung benötigt die binäre Suche? (Eine sortierte Datenmenge) (!Eine unsortierte Datenmenge) (!Eine leere Datenmenge) (!Eine zufällig veränderte Datenmenge)

Was bedeutet Worst Case? (Der ungünstigste betrachtete Eingabefall) (!Der schönste Programmcode) (!Der kürzeste Dateiname) (!Der erste erfolgreiche Testlauf)

Welche Ordnung ist typisch für viele effiziente vergleichsbasierte Sortierverfahren? (O n log n) (!O n hoch drei) (!O zwei hoch n) (!O n Fakultät)

Was beschreibt die Speicherkomplexität? (Den zusätzlichen Speicherbedarf eines Algorithmus) (!Die Bildschirmauflösung eines Programms) (!Die Anzahl der Entwicklerinnen und Entwickler) (!Die Länge des Programmnamens)

Warum werden konstante Faktoren in der asymptotischen Analyse oft weggelassen? (Weil das Wachstum für große Eingaben im Mittelpunkt steht) (!Weil sie in Programmen verboten sind) (!Weil Computer keine Konstanten speichern können) (!Weil sie immer größer als n sind)

Was ist ein typisches Merkmal logarithmischer Laufzeit? (Der Suchbereich wird wiederholt stark verkleinert) (!Alle Permutationen werden ausprobiert) (!Jedes Element wird mit jedem anderen verglichen) (!Der Speicher wird absichtlich gelöscht)

Was leistet die amortisierte Analyse? (Sie betrachtet die durchschnittlichen Kosten über eine Operationsfolge) (!Sie ersetzt jeden Algorithmus durch Zufall) (!Sie misst nur die Temperatur der Hardware) (!Sie bewertet nur die Farbe von Diagrammen)

Memory

Landau-Symbol	Wachstumsbeschreibung
Worst Case	Ungünstigster Fall
Binäre Suche	Halbierter Suchbereich
Speicherkomplexität	Zusatzspeicher
Rekursion	Selbstaufruf
Lineare Suche	Elementweises Prüfen
Quicksort	Teile-und-herrsche
Asymptotik	Verhalten bei großen Eingaben

Drag and Drop

Ordne die richtigen Begriffe zu.	Thema
Konstante Laufzeit	Aufwand bleibt unabhängig von der Eingabegröße
Logarithmische Laufzeit	Suchbereich wird wiederholt verkleinert
Lineare Laufzeit	Jedes Element wird einmal betrachtet
Quadratische Laufzeit	Zwei vollständige Schleifen sind verschachtelt
Exponentielle Laufzeit	Aufwand wächst besonders schnell mit jedem weiteren Element

Kreuzworträtsel

Asymptotik	Wie heißt die Betrachtung des Verhaltens bei sehr großen Eingaben?
Laufzeit	Welche Ressource beschreibt die benötigte Rechenzeit?
Speicher	Welche Ressource beschreibt den benötigten Platz im Arbeitsspeicher?
Rekursion	Wie heißt ein Verfahren, bei dem sich eine Methode selbst aufruft?
Iteration	Wie heißt die wiederholte Ausführung mit Schleifen?
Sortieren	Wie heißt das Anordnen von Daten nach einer Ordnung?

LearningApps

Lückentext

Die Algorithmenanalyse untersucht den

von Algorithmen. Die wichtigste Eingabegröße wird häufig mit

bezeichnet. Eine einfache Schleife über alle Elemente führt oft zu

Laufzeit. Bei der binären Suche wird der Suchbereich wiederholt

. Der ungünstigste Eingabefall heißt

. Der günstigste Eingabefall heißt

. Die asymptotische Analyse betrachtet vor allem das Verhalten bei

Eingaben. Das Symbol O beschreibt eine

Schranke. Die Speicherkomplexität untersucht den zusätzlichen

. Bei rekursiven Algorithmen helfen oft

.

Offene Aufgaben

Leicht

Alltagsalgorithmus: Beschreibe einen Algorithmus aus Deinem Alltag, zum Beispiel Zähneputzen, Brotbacken oder das Suchen eines Buches, und erkläre, welche Eingabegröße dabei sinnvoll sein könnte.
Lineare Suche: Erstelle eine kleine Liste mit zehn Namen und zeige Schritt für Schritt, wie eine lineare Suche im Best Case und im Worst Case abläuft.
Laufzeitklassen: Zeichne ein Lernplakat, das konstante, logarithmische, lineare und quadratische Laufzeit mit eigenen Beispielen erklärt.
Pseudocode: Schreibe Pseudocode für das Finden der größten Zahl in einer Liste und markiere die Operation, die bei der Analyse gezählt werden soll.

Standard

Schleifenanalyse: Analysiere drei kurze Programme mit einfachen und verschachtelten Schleifen und begründe jeweils die vermutete Laufzeitordnung.
Binäre Suche: Vergleiche lineare Suche und binäre Suche an einer sortierten Liste mit 32 Elementen und dokumentiere die maximale Anzahl der Vergleiche.
Sortierverfahren: Recherchiere Bubble Sort, Insertion Sort und Merge Sort in OER-Quellen und erstelle eine Tabelle mit Idee, Laufzeit und Speicherbedarf.
Messung und Analyse: Implementiere ein einfaches Suchverfahren und miss die Laufzeit für verschiedene Eingabegrößen. Vergleiche Deine Messwerte mit der theoretischen Erwartung.

Schwer

Rekursionsgleichung: Analysiere einen rekursiven Algorithmus, der ein Problem halbiert, und erkläre mit eigenen Worten, warum eine logarithmische Laufzeit entstehen kann.
Trade-off: Entwickle ein Beispiel, bei dem zusätzlicher Speicher die Laufzeit verbessert, und diskutiere die Vor- und Nachteile.
Graphalgorithmus: Beschreibe eine Breitensuche in einem selbst gezeichneten Graphen und erkläre, warum Knoten und Kanten für die Analyse wichtig sind.
Algorithmusvergleich: Wähle zwei Algorithmen für dasselbe Problem, vergleiche sie nach Laufzeit, Speicherbedarf, Verständlichkeit und praktischer Eignung und begründe eine Empfehlung.

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

Lernkontrolle

Transferaufgabe: Ein Online-Shop muss Produkte in einer großen Datenbank suchen. Erkläre, warum eine lineare Suche problematisch sein kann und welche Rolle Sortierung oder Indexierung spielen könnte.
Fallanalyse: Ein Algorithmus ist bei kleinen Eingaben schneller, hat aber eine schlechtere Wachstumsordnung als ein zweiter Algorithmus. Entscheide, welcher Algorithmus für sehr große Eingaben besser geeignet ist, und begründe Deine Entscheidung.
Komplexitätsvergleich: Vergleiche O(n), O(n log n), O(n²) und O(2ⁿ) in einem selbst gewählten Szenario und erkläre die praktischen Folgen.
Rekursionsverständnis: Erkläre an einem Beispiel, wie Rekursion die Laufzeit beeinflussen kann, und unterscheide dabei zwischen einem und mehreren rekursiven Aufrufen.
Zeit-Speicher-Abwägung: Entwirf eine Situation, in der mehr Speicher zu weniger Laufzeit führt, und bewerte, ob sich dieser Tausch lohnt.
Modellkritik: Diskutiere, warum eine theoretische Laufzeitanalyse trotz moderner Hardware wichtig bleibt und wo ihre Grenzen liegen.

Lernnachweis

Für einen Lernnachweis sollst Du zeigen, dass Du nicht nur Begriffe wiedergeben, sondern Zusammenhänge anwenden kannst. Bearbeite dazu eine eigene Analyseaufgabe.

Algorithmusauswahl: Wähle ein Problem, für das es mindestens zwei Lösungswege gibt, zum Beispiel Suchen, Sortieren oder Duplikate finden.
Pseudocode: Beschreibe beide Lösungswege so genau, dass eine andere Person sie nachvollziehen kann.
Analyse: Bestimme für beide Lösungswege eine plausible Laufzeitordnung und eine plausible Speicherkomplexität.
Begründung: Erkläre, welche Eingabegröße Du verwendest und warum.
Reflexion: Entscheide, welcher Lösungsweg für kleine, mittlere und große Eingaben jeweils sinnvoll ist.

Bewertungskriterien sind fachliche Richtigkeit, nachvollziehbare Begründung, saubere Verwendung der Begriffe, passende Beispiele und eine reflektierte Entscheidung.

OERs zum Thema

Ergänzende OER- und Recherchehinweise:

Links

Algorithmenanalyse

Zusammenfassung

Die Algorithmenanalyse beschreibt, wie der Aufwand eines Algorithmus mit wachsender Eingabegröße zunimmt. Sie unterscheidet Laufzeit, Speicherkomplexität, günstige und ungünstige Eingabefälle sowie praktische und theoretische Betrachtungen. Mit Landau-Symbolen werden Wachstumsordnungen wie O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) und O(n!) beschrieben. Dadurch kannst Du Algorithmen vergleichen, Grenzen erkennen und begründete Entscheidungen für Programme und Datenstrukturen treffen.

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.