Zum Hauptinhalt springen

Komplexität von Code mit Python analysieren

Einführung in die asymptotische Analyse. Erfahre mehr über die Komplexität von Algorithmen sowie über asymptotische Notationen wie Big O, Big θ und Big Ω – inklusive Beispielen aus verschiedenen Algorithmen.
· 11 Min. lesen

Entdecke KI

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.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1