Glanz: aiMOOC über GPT aiMOOC Action erstellt

2026-06-17T16:16:48Z

aiMOOC über GPT aiMOOC Action erstellt

Neue Seite

{{T}}

{{BR}}
= Algorithmusanalyse =

{{BR}}
== Einleitung ==

'''[[Algorithmusanalyse]]''' untersucht, wie viel [[Rechenzeit]], [[Speicherplatz]] und andere [[Ressource|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 [[Datenstruktur|Datenstrukturen]] und [[Sortieralgorithmus|Sortieralgorithmen]] analysiert werden. Du lernst außerdem, einfache [[Pseudocode|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 [[Suchmaschine|Suchmaschinen]], [[Kryptographie]], [[Datenbank|Datenbanken]], [[Künstliche Intelligenz]], [[Bioinformatik]] und [[Netzwerk|Netzwerken]] entscheidet die Wahl des Algorithmus oft über die praktische Machbarkeit.

{{BR}}
== 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-Tabelle|Hash-Tabellen]] in verschiedenen Situationen unterschiedlich geeignet sind.

{{BR}}
== 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 [https://commons.wikimedia.org/w/index.php?search=computational+complexity&title=Special:MediaSearch&type=image Wikimedia Commons: computational complexity].
# [[Wikipedia]] und [[OER]]: Lies ergänzend die Artikel [https://de.wikipedia.org/wiki/Algorithmusanalyse Wikipedia: Algorithmusanalyse], [https://de.wikipedia.org/wiki/Landau-Symbole Wikipedia: Landau-Symbole] und [https://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie Wikipedia: Komplexitätstheorie].
# [[Lernvideo]]: Suche nach deutschsprachigen Erklärvideos über [https://www.youtube.com/results?search_query=Algorithmusanalyse+Big+O+Notation+deutsch YouTube: Algorithmusanalyse Big O Notation deutsch].
# [[Interaktive Visualisierung]]: Nutze Visualisierungen zu Sortieralgorithmen, z. B. über [https://visualgo.net/en/sorting VisuAlgo: Sorting], um Laufzeitverhalten praktisch zu beobachten.

{{BR}}
= Grundlagen der Algorithmusanalyse =

{{BR}}
== 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.

{{BR}}
== 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 [[Graph|Graphen]] die Anzahl der [[Knoten]] und [[Kante|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.

{{BR}}
== 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.

{{BR}}
== Maschinelles Messen und theoretisches Analysieren ==

Man kann Algorithmen praktisch messen, indem man Programme ausführt und Zeiten stoppt. Solche [[Benchmark|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.

{{BR}}
= Asymptotische Notation =

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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).

{{BR}}
== 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.

{{BR}}
== 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.

{| class="wikitable"
! 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
|}

{{BR}}
= Fälle der Laufzeitanalyse =

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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).

{{BR}}
= Analyse einfacher Programmstrukturen =

{{BR}}
== 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.

{{BR}}
== Einfache Schleifen ==

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

{| class="wikitable"
! 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).

{{BR}}
== 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.

{| class="wikitable"
! 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
|}

{{BR}}
== Bedingungen und Verzweigungen ==

Bei einer [[Bedingte Anweisung|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.

{{BR}}
== 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.

{{BR}}
= Beispiele wichtiger Algorithmen =

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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 [[Kollision|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.

{{BR}}
= Grenzen der Effizienz =

{{BR}}
== 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.

{{BR}}
== 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 (Komplexitätsklasse)|P]], [[NP (Komplexitätsklasse)|NP]] und [[NP-Vollständigkeit]]. Die berühmte Frage [[P-NP-Problem|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.

{{BR}}
== 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.

{{BR}}
= Vorgehensweise bei der Analyse =

{{BR}}
== 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.

{{BR}}
== Beispielanalyse ==

Gegeben sei folgender Pseudocode:

{| class="wikitable"
|-
| 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).

{{BR}}
== 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.

{{BR}}
= Interaktive Aufgaben =

{{BR}}
== Quiz: Teste Dein Wissen ==

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{BR}}
== Memory ==

<div class="memo-quiz">
{|
|-
| 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
|}
{{E}}
<br>

{{BR}}
== Drag and Drop ==

<div class="lueckentext-quiz">

{| class="wikitable"
! 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
|}
{{E}}

<br>
<br />

{{BR}}
== Kreuzworträtsel ==

<div class="kreuzwort-quiz">
{|
|-
| 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?
|}
{{E}}
<br>

{{BR}}
== LearningApps ==

<iframe> https://learningapps.org/index.php?s=Algorithmusanalyse </iframe>

{{BR}}
== Lückentext ==

<quiz display=simple>
{'''Vervollständige den Text.'''<br>
|type="{}"}
Die Algorithmusanalyse untersucht den { Ressourcenbedarf } eines Algorithmus in Abhängigkeit von der Eingabegröße. Die Eingabegröße wird häufig mit { n } bezeichnet. Die O-Notation beschreibt eine asymptotische { obere } Schranke. Die Omega-Notation beschreibt eine asymptotische { untere } Schranke. Eine enge Schranke wird mit der { Theta-Notation } beschrieben. Bei der binären Suche wird der Suchbereich in jedem Schritt ungefähr { halbiert }. Eine lineare Suche benötigt im Worst Case { O(n) } Schritte. Mergesort hat typischerweise die Laufzeit { O(n log n) }. Bei einer Hash-Tabelle sind Suchoperationen im Durchschnitt oft { O(1) }. Die amortisierte Analyse betrachtet die Kosten über eine { Folge } von Operationen.
</quiz>

<br>

{{BR}}
= Offene Aufgaben =

{{BR}}
=== 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.

{{BR}}
=== 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.

{{BR}}
=== 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 [[Datenbank|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.

{{:Offene Aufgabe - MOOC erstellen}}

{{BR}}
= 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.

{{BR}}
= 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.

<br>
<br>

{{BR}}
= OERs zum Thema =

<iframe> https://de.m.wikipedia.org/wiki/Algorithmusanalyse </iframe>

Weitere freie Lern- und Recherchequellen:
# [[Wikipedia]]: [https://de.wikipedia.org/wiki/Landau-Symbole Landau-Symbole] zur mathematischen Notation asymptotischer Schranken.
# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=algorithm+analysis&title=Special:MediaSearch&type=image Medienrecherche zu algorithm analysis].
# [[OER-Suche]]: [https://open-educational-resources.de/?s=Algorithmusanalyse OERinfo-Suche zu Algorithmusanalyse].
# [[Lernvideo-Suche]]: [https://www.youtube.com/results?search_query=Algorithmusanalyse+Laufzeit+O-Notation+deutsch YouTube-Suche zu Laufzeit und O-Notation].

<br>

{{BR}}
= Links =

{| align=center
{{:D-Tab}}
'''[[Algorithmusanalyse]]'''
# [[Algorithmus]]
# [[O-Notation]]
# [[Landau-Symbole]]
# [[Laufzeit]]
# [[Speicherkomplexität]]
# [[Eingabegröße]]
# [[Worst Case]]
# [[Average Case]]
# [[Best Case]]
# [[Binäre Suche]]
# [[Lineare Suche]]
# [[Sortieralgorithmus]]
# [[Mergesort]]
# [[Quicksort]]
# [[Hash-Tabelle]]
# [[Komplexitätstheorie]]
|}

{{BR}}
= 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.

[[Kategorie:Informatik]]
[[Kategorie:Algorithmus]]
[[Kategorie:Programmierung]]
[[Kategorie:Mathematik]]
[[Kategorie:Sekundarstufe II]]
[[Kategorie:Studium]]
[[Kategorie:Medienbildung]]

{{BR}}
= aiMOOC-Projekte =
[[Kategorie:AI_MOOC]] [[Kategorie:GPT aiMOOC]]
{{MT}}

Algorithmusanalyse - Versionsgeschichte

Glanz: aiMOOC über GPT aiMOOC Action erstellt