Question 1

Was versteht man unter der Komplexität von Algorithmen?

Accepted Answer

Die Komplexität von Algorithmen beschreibt, wie sich der Ressourcenverbrauch (Zeit oder Speicher) eines Algorithmus in Abhängigkeit von der Eingabegröße verhält. Sie hilft dabei, die Effizienz verschiedener Algorithmen zu vergleichen und das Verhalten bei großen Datenmengen vorherzusagen.

Question 2

Was ist die O-Notation und wofür wird sie verwendet?

Accepted Answer

Die O-Notation (Big-O-Notation) ist eine mathematische Schreibweise zur Beschreibung der oberen Schranke der Laufzeit eines Algorithmus. Sie gibt an, wie stark die Laufzeit maximal mit der Eingabegröße n wächst, beispielsweise O(n) für lineares oder O(n²) für quadratisches Wachstum.

Question 3

Was bedeutet Worst-Case-Analyse?

Accepted Answer

Die Worst-Case-Analyse betrachtet das schlechteste Szenario für einen Algorithmus, also die Eingabe, die zur längsten Laufzeit führt. Sie garantiert, dass der Algorithmus niemals länger als die berechnete Zeit benötigt, und ist daher besonders wichtig für kritische Anwendungen.

Question 4

Welche häufigen Komplexitätsklassen gibt es?

Accepted Answer

Die wichtigsten Komplexitätsklassen sind O(1) für konstante Zeit, O(log n) für logarithmische, O(n) für lineare, O(n log n) für linearithmische und O(n²) für quadratische Laufzeit. O(2^n) beschreibt exponentielles Wachstum, das bei großen Eingaben sehr ineffizient wird.

Question 5

Wie führt man eine einfache Laufzeitanalyse durch?

Accepted Answer

Bei der Laufzeitanalyse zählt man die elementaren Operationen (Vergleiche, Zuweisungen) in Abhängigkeit von der Eingabegröße n. Schleifen werden entsprechend ihrer Durchlaufanzahl gewichtet, und am Ende bestimmt der Term mit dem stärksten Wachstum die Komplexitätsklasse.

Algorithmus-Komplexität: O-Notation & Laufzeitanalyse

Lernkarten zu Komplexität von Algorithmen