Die Komplexität eines Algorithmus misst, wie viel Zeit und/oder Speicher ein Algorithmus für eine Eingabe einer bestimmten Größe (n) benötigt. Sie hängt zwar auch von Faktoren wie der Rechnerarchitektur, also der Hardwareplattform, der Darstellung der abstrakten Datentypen (ADT), der Compiler-Effizienz, der Komplexität des zugrunde liegenden Algorithmus und der Eingabegröße ab. Am stärksten wirken sich in der Praxis jedoch die Komplexität des Algorithmus selbst und die Größe der Eingabe aus.
Im DataCamp-Blog Python Data Structures Tutorial findest du eine grundlegende Einführung in Datenstrukturen und ihre Implementierung in Python. Der Beitrag erklärt abstrakte Datentypen und Datenstrukturen, primitive und nicht-primitive Datenstrukturen.
Asymptotische Analyse
Bei der asymptotischen Analyse wird die Laufzeit eines Codes oder einer Operation in mathematischen Einheiten einer Berechnung ermittelt. Man beschreibt sie als Funktion f(n). In der mathematischen Analyse ist die Asymptotik eine Methode, Grenzverhalten zu beschreiben.
Für die von einem Algorithmus benötigte Zeit betrachtet man drei Fälle: Worst Case – die maximale Laufzeit, die am häufigsten zur Analyse herangezogen wird. Best Case – die minimale Laufzeit, die bei der Analyse meist weniger relevant ist. Average Case – die mittlere Laufzeit, die je nach Kontext ebenfalls betrachtet wird.
Asymptotische Notation
Gängige Notationen zur Beschreibung der Laufzeitkomplexität eines Algorithmus sind:
- Big-O-Notation
- Big-θ-Notation
- Big-Ω-Notation
Big-O-Notation, Ο
Big O misst die Performance bzw. Komplexität eines Algorithmus. Mathematisch ist sie die obere Schranke der Wachstumsrate einer Funktion: Wächst eine Funktion g(x) nicht schneller als eine Funktion f(x), dann gehört g zu O(f). Typischerweise gibt Big O die obere Schranke eines Algorithmus an und damit seine Worst-Case-Komplexität – also die längste mögliche Laufzeit bis zum Abschluss.
Big-Omega-Notation, Ω
Die Notation Ω(n) beschreibt formal die untere Schranke der Laufzeit eines Algorithmus. Sie misst die Best-Case-Komplexität, also die kürzeste mögliche Laufzeit.
Big-Theta-Notation, θ
Die Notation θ(n) beschreibt formal sowohl die untere als auch die obere Schranke der Laufzeit eines Algorithmus.
Wie die Notationen zur Komplexitätsbestimmung eingesetzt werden
Am häufigsten verwendet man Big O, um die obere Schranke eines Algorithmus zu bestimmen. Big θ kommt mitunter zum Einsatz, um den durchschnittlichen Fall zu charakterisieren, und die Ω-Notation wird vergleichsweise selten genutzt.
Im Folgenden siehst du Beispiele, wie diese Notationen zur Bestimmung der Komplexität konkreter Algorithmen eingesetzt werden.
Beispiel Quicksort:
Quicksort ist ein Divide-and-Conquer-Algorithmus zum Sortieren. Er ordnet Elemente systematisch, etwa Zahlen in einem Array in auf- oder absteigender Reihenfolge. Der Algorithmus wählt ein Pivot-Element aus dem Array. Das Pivot kann auf verschiedene Arten gewählt werden; im folgenden Beispiel ist es das letzte Element.
Das Herzstück von Quicksort ist die Partitionierung. Aus dem Array wird ein Pivotelement gewählt. Dieses wird an die korrekte Position gebracht; alle größeren Elemente kommen rechts vom Pivot, alle kleineren links davon.
def partition(array,low,high):
i = ( low-1 )
pivot = array[high]
for j in range(low , high):
if array[j] <= pivot:
i = i+1
array[i],array[j] = array[j],array[i]
array[i+1],array[high] = array[high],array[i+1]
return ( i+1 )
def quickSort(array,low,high):
if low < high:
pit = partition(array,low,high)
quickSort(array, low, pit-1
Die Komplexität eines Algorithmus misst, wie viel Zeit und/oder Speicher ein Algorithmus für eine Eingabe einer bestimmten Größe (n) benötigt. Sie hängt zwar auch von Faktoren wie der Rechnerarchitektur, also der Hardwareplattform, der Darstellung der abstrakten Datentypen (ADT), der Compiler-Effizienz, der Komplexität des zugrunde liegenden Algorithmus und der Eingabegröße ab. Am stärksten wirken sich in der Praxis jedoch die Komplexität des Algorithmus selbst und die Größe der Eingabe aus.
Im DataCamp-Blog Python Data Structures Tutorial findest du eine grundlegende Einführung in Datenstrukturen und ihre Implementierung in Python. Der Beitrag erklärt abstrakte Datentypen und Datenstrukturen, primitive und nicht-primitive Datenstrukturen.
Asymptotische Analyse
Bei der asymptotischen Analyse wird die Laufzeit eines Codes oder einer Operation in mathematischen Einheiten einer Berechnung ermittelt. Man beschreibt sie als Funktion f(n). In der mathematischen Analyse ist die Asymptotik eine Methode, Grenzverhalten zu beschreiben.
Für die von einem Algorithmus benötigte Zeit betrachtet man drei Fälle: Worst Case – die maximale Laufzeit, die am häufigsten zur Analyse herangezogen wird. Best Case – die minimale Laufzeit, die bei der Analyse meist weniger relevant ist. Average Case – die mittlere Laufzeit, die je nach Kontext ebenfalls betrachtet wird.
Asymptotische Notation
Gängige Notationen zur Beschreibung der Laufzeitkomplexität eines Algorithmus sind:
Big-O-Notation, Ο
Big O misst die Performance bzw. Komplexität eines Algorithmus. Mathematisch ist sie die obere Schranke der Wachstumsrate einer Funktion: Wächst eine Funktion g(x) nicht schneller als eine Funktion f(x), dann gehört g zu O(f). Typischerweise gibt Big O die obere Schranke eines Algorithmus an und damit seine Worst-Case-Komplexität – also die längste mögliche Laufzeit bis zum Abschluss.
Big-Omega-Notation, Ω
Die Notation Ω(n) beschreibt formal die untere Schranke der Laufzeit eines Algorithmus. Sie misst die Best-Case-Komplexität, also die kürzeste mögliche Laufzeit.
Big-Theta-Notation, θ
Die Notation θ(n) beschreibt formal sowohl die untere als auch die obere Schranke der Laufzeit eines Algorithmus.
Wie die Notationen zur Komplexitätsbestimmung eingesetzt werden
Am häufigsten verwendet man Big O, um die obere Schranke eines Algorithmus zu bestimmen. Big θ kommt mitunter zum Einsatz, um den durchschnittlichen Fall zu charakterisieren, und die Ω-Notation wird vergleichsweise selten genutzt.
Im Folgenden siehst du Beispiele, wie diese Notationen zur Bestimmung der Komplexität konkreter Algorithmen eingesetzt werden.
Beispiel Quicksort:
Quicksort ist ein Divide-and-Conquer-Algorithmus zum Sortieren. Er ordnet Elemente systematisch, etwa Zahlen in einem Array in auf- oder absteigender Reihenfolge. Der Algorithmus wählt ein Pivot-Element aus dem Array. Das Pivot kann auf verschiedene Arten gewählt werden; im folgenden Beispiel ist es das letzte Element.
Das Herzstück von Quicksort ist die Partitionierung. Aus dem Array wird ein Pivotelement gewählt. Dieses wird an die korrekte Position gebracht; alle größeren Elemente kommen rechts vom Pivot, alle kleineren links davon.