Komplexität von Code mit Python analysieren

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)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

The Sorted array is:
2
4
6
8
10
12
Du erhältst die Ausgabe:

The Sorted array is: 2 4 6 8 10 12

Jetzt zur Analyse der Zeitkomplexität. Zunächst:

• Best Case: Ω(n log n)
• Average Case: Θ(n log n)
• Worst Case: O(n^2)

Schauen wir uns den obigen Code an.

Best Case: Der Best Case tritt ein, wenn das Pivotelement jeweils ungefähr in der Mitte liegt. Der Algorithmus ruft sich dann rekursiv auf der ersten und zweiten Hälfte auf. Die Anzahl der Schritte entspricht der Anzahl der Teilungen von n auf 1, wenn du das Problem in jedem Schritt halbierst: n / 2^k = 1. Da 2^{log n} = n gilt, folgt k = log n. Die Anzahl der Iterationen ist also O(log n); da jede Iteration O(n) kostet, ergibt sich insgesamt O(n log n).

Average Case: Für den Durchschnittsfall betrachtet man alle Permutationen des Arrays und bestimmt die jeweilige Laufzeit. Mehr dazu findest du bei Merge sort.

Worst Case: Im Worst Case wird als Pivot immer ein schlechtes Element gewählt (z. B. erstes oder letztes bei bereits sortierten Eingaben). Nach der Partition ist dann eine Teilmenge von Größe 1 und die andere von Größe n-1. Mit T(n) als Laufzeitfunktion gilt: T(n) = T(n-1) + O(n) ⇒ T(n) = O(n^2).

Beispiele

Der folgende Code ist simpel und du würdest ihn vielleicht nicht spontan „Algorithmus“ nennen – technisch ist aber jeder Code zur Lösung eines Problems ein Algorithmus. Hier ist es eine for-Schleife mit einer einzelnen Print-Anweisung:

print('I love Python');

Hello world!
Die Zeitkomplexität des obigen „Algorithmus“ ist O(1), da stets genau ein Schritt ausgeführt wird. Es ist konstante Zeit.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Wie würdest du die Effizienz des obigen Algorithmus in Big-O-Notation beschreiben?

Zur Analyse zählst du die Schritte. Im Beispiel enthält die Liste vier Elemente, und jedes wird genau einmal ausgegeben. Was passiert, wenn die Liste größer ist, z. B. 15 Elemente? Nimmt die Schleife dann gleich viele Schritte? Da diese for-Schleife so viele Schritte macht, wie es Elemente gibt, hat der Algorithmus die Effizienz O(n) und nicht O(1).

Als Nächstes ein einfacher Python-Algorithmus, der prüft, ob eine Zahl prim ist:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

Der Code nimmt eine Zahl entgegen und startet eine for-Schleife, in der jede Zahl von 2 bis zur Zahl selbst als Teiler geprüft wird. Gibt es keinen Rest, ist die Zahl nicht prim und die Funktion gibt sofort False zurück. Wenn du bis zur Zahl kommst und immer ein Rest auftritt, ist die Zahl prim und die Funktion gibt True zurück.

Die Effizienz dieses Algorithmus ist O(n). Die Eingabe ist hier keine Liste, sondern die Zahl selbst. Für 11 läuft die Schleife ungefähr elf Schritte (tatsächlich neun, da bei 2 gestartet und vor der Zahl aufgehört wird). Für 101 sind es etwa 101 Schritte. Da die Schrittzahl proportional zur Eingabe wächst, ist dies ein klassisches Beispiel für O(n).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Die Komplexität ist O(n). Die zweite Schleife mit 100 Iterationen ist eine Konstante und wird bei der asymptotischen Betrachtung vernachlässigt, da n als sehr groß angenommen wird.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

Es gibt zwei Schleifen mit Längen m und n. Für große m und n ist die Komplexität O(n + m). Da die Schleifen unabhängig sind und unterschiedliche Eingaben haben, addieren sich die Aufwände.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

Hier sind die Schleifen geschachtelt. Für große n und m ist die Komplexität O(n*m). Da die Schleifen ineinander liegen, multiplizieren sich die Aufwände.

Glückwunsch!

Du hast das Ende dieses Tutorials erreicht! Unterwegs hast du die asymptotische Notation kennengelernt – ein Grundwerkzeug für Programmiererinnen, Programmierer und Data Scientists. Du hast eine einfache, verständliche Vorgehensweise zur Komplexitätsanalyse gesehen – ohne viel Fachjargon oder mathematische Strenge. Auch wenn Datenstrukturen und Algorithmen oft im Informatikstudium gelehrt werden, ist Grundwissen darüber für alle hilfreich. Für einen tieferen Einstieg lohnt sich dieser Kurs: MIT OpenCourseWare Algorithmus-Kurs

Wenn du mehr über Python lernen möchtest, sieh dir diese DataCamp-Kurse an: