Glanz: aiMOOC über GPT aiMOOC Action erstellt

2026-06-17T14:45:35Z

aiMOOC über GPT aiMOOC Action erstellt

Neue Seite

{{T}}

{{BR}}
= Algorithmenanalyse =

'''[[Algorithmenanalyse]]''' untersucht, wie viele [[Ressource|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.

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

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

# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=algorithm+flowchart+complexity&title=Special:MediaSearch&type=image Commons-Mediensuche zu Algorithmus, Flussdiagramm und Komplexität]
# [[Wikipedia]]: [https://de.wikipedia.org/wiki/Algorithmenanalyse Wikipedia-Suche bzw. Artikel zu Algorithmenanalyse]
# [[Wikipedia]]: [https://de.wikipedia.org/wiki/Landau-Symbole Artikel zu Landau-Symbolen]
# [[Wikibooks]]: [https://de.wikibooks.org/w/index.php?search=Algorithmus+Laufzeit+Sortierverfahren&title=Spezial:Suche&fulltext=1 OER-Suche zu Algorithmen, Laufzeit und Sortierverfahren]
# [[YouTube]]: [https://www.youtube.com/results?search_query=Algorithmenanalyse+Laufzeit+Big+O+deutsch Lernvideosuche zu Algorithmenanalyse, Laufzeit und Big O]

{{BR}}
= Grundlagen =

{{BR}}
== 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 [[lineare Suche|linearer Suche]] und linearer Laufzeit.

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

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

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

{{BR}}
= Laufzeitanalyse =

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

<pre>
summe = 0
für jedes element in liste:
summe = summe + element
</pre>

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

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

<pre>
für i von 1 bis n:
für j von 1 bis n:
vergleiche element i mit element j
</pre>

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

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

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

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

{{BR}}
= Asymptotische Analyse =

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

{{BR}}
== Landau-Symbole ==

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

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

{{BR}}
== Typische Wachstumsordnungen ==

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

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

{{BR}}
= Speicherkomplexität =

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

{{BR}}
== Zeit-Speicher-Abwägung ==

In vielen Situationen gibt es einen [[Trade-off|Zeit-Speicher-Trade-off]]. Zusätzlicher Speicher kann Laufzeit sparen, etwa durch [[Hash-Tabelle|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.

{{BR}}
= Beispiele der Algorithmenanalyse =

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

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

{{BR}}
== Binäre Suche ==

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

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

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

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

{{BR}}
== Graphalgorithmen ==

Bei [[Graphalgorithmus|Graphalgorithmen]] hängt die Analyse häufig von zwei Größen ab: der Anzahl der [[Knoten]] und der Anzahl der [[Kante|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.

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

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

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

{{BR}}
= Interaktive Aufgaben =

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

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{BR}}
== Memory ==

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

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

<div class="lueckentext-quiz">

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

|}
{{E}}

<br>
<br />

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

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

{{BR}}
== LearningApps ==

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

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

<quiz display=simple>
{'''Vervollständige den Text.'''<br>
|type="{}"}
Die Algorithmenanalyse untersucht den { Ressourcenbedarf } von Algorithmen. Die wichtigste Eingabegröße wird häufig mit { n } bezeichnet. Eine einfache Schleife über alle Elemente führt oft zu { linearer } Laufzeit. Bei der binären Suche wird der Suchbereich wiederholt { halbiert }. Der ungünstigste Eingabefall heißt { Worst Case }. Der günstigste Eingabefall heißt { Best Case }. Die asymptotische Analyse betrachtet vor allem das Verhalten bei { großen } Eingaben. Das Symbol O beschreibt eine { obere } Schranke. Die Speicherkomplexität untersucht den zusätzlichen { Speicherbedarf }. Bei rekursiven Algorithmen helfen oft { Rekursionsgleichungen }.
</quiz>

<br>

{{BR}}
= Offene Aufgaben =

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

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

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

{{:Offene Aufgabe - MOOC erstellen}}

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

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

<br>
<br>

{{BR}}
= OERs zum Thema =

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

Ergänzende OER- und Recherchehinweise:

# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=algorithm+complexity+Big+O&title=Special:MediaSearch&type=image Bilder und Diagramme zu Algorithmenkomplexität]
# [[Wikipedia]]: [https://de.wikipedia.org/wiki/Landau-Symbole Landau-Symbole]
# [[Wikipedia]]: [https://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie Komplexitätstheorie]
# [[Wikibooks]]: [https://de.wikibooks.org/w/index.php?search=Algorithmus+Analyse&title=Spezial:Suche&fulltext=1 Wikibooks-Suche zu Algorithmusanalyse]
# [[YouTube]]: [https://www.youtube.com/results?search_query=Big+O+Notation+deutsch+Algorithmenanalyse Lernvideosuche zu Big-O-Notation und Algorithmenanalyse]

<br>

{{BR}}
= Links =

{| align=center
{{:D-Tab}}
'''[[Algorithmenanalyse]]'''
# [[Algorithmus]]
# [[Laufzeitanalyse]]
# [[Speicherkomplexität]]
# [[Landau-Symbole]]
# [[Asymptotik]]
# [[Datenstruktur]]
# [[Sortierverfahren]]
# [[Suchalgorithmus]]
# [[Binäre Suche]]
# [[Lineare Suche]]
# [[Rekursion]]
# [[Komplexitätstheorie]]
|}

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

[[Kategorie:Informatik]]
[[Kategorie:Programmieren]]
[[Kategorie:Algorithmus]]
[[Kategorie:Algorithmenanalyse]]
[[Kategorie:Datenstrukturen]]
[[Kategorie:Mathematik]]
[[Kategorie:Sekundarstufe II]]
[[Kategorie:Studium]]
[[Kategorie:Berufliche Bildung]]

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

Algorithmenanalyse - Versionsgeschichte

Glanz: aiMOOC über GPT aiMOOC Action erstellt