Die Zeitkomplexität eines Codes gibt an, wie die Laufzeit des Algorithmus mit der Größe der Eingabedaten wächst. Um die Zeitkomplexität zu bestimmen, betrachten wir die Anzahl der Operationen, die der Algorithmus in Abhängigkeit von der Größe der Eingabe ausführt.

Schritte zur Analyse der Zeitkomplexität

1. Identifiziere die grundlegenden Operationen:

   • Bestimme die häufigsten Operationen im Code, z.B. Vergleiche, Zuweisungen und Schleifen.

2. Zähle die Anzahl der Operationen:

   • Analysiere, wie viele grundlegende Operationen in Abhängigkeit von der Eingabegröße ( n ) ausgeführt werden.

3. Bestimme die Dominante:

   • Finde die am schnellsten wachsende Funktion (dominant) in deiner Zählung. Diese wird die Zeitkomplexität bestimmen.

4. Verwende die Big O-Notation:

   • Schreibe die Zeitkomplexität in der Big O-Notation, um die obere Schranke der Laufzeit auszudrücken.

Bsp

Hier ist ein Beispiel für einen einfachen Python-Code, der die Zeitkomplexität analysiert:

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

Schritt-für-Schritt-Analyse:

1. Identifiziere die grundlegenden Operationen:

   • Die grundlegende Operation ist die Addition (total += num).

2. Zähle die Anzahl der Operationen:

   • Die Schleife läuft ( n ) Mal, wobei ( n ) die Anzahl der Elemente im Array ist.

3. Bestimme die Dominante:

   • Die Anzahl der Operationen ist also proportional zu ( n ), also ( 4. Big O(n) ).

4. Schreibe die Big O-Notation:

   • Die Zeitkomplexität von sum_array ist ( 4. Big O(n) ).

Regeln zur Bestimmung der Zeitkomplexität

1. Schleifen:

   • Eine einfache Schleife von 1 bis ( n ) hat eine Zeitkomplexität von ( 4. Big O(n) ).
   • Verschachtelte Schleifen führen die Zeitkomplexität zu ( O(n^2) ) (z.B. zwei Schleifen, die beide von 1 bis ( n ) laufen).

2. Rekursion:

   • Bei rekursiven Funktionen zählt man die Anzahl der rekursiven Aufrufe. Der Zeitkomplexitätsausdruck ergibt sich oft aus der Rekursionsbeziehung.

3. Bestimmte Operationen:

   • Hinzufügen, Entfernen und Zugreifen auf ein Element in einer Liste oder einem Array sind ( 1. Big O(1) ).
   • Suchen in einer nicht sortierten Liste hat eine Zeitkomplexität von ( 4. Big O(n) ), während die Suche in einer sortierten Liste mit binärer Suche ( 2. Big O(log n) ) hat.

Gesamte Zeitkomplexität berechnen

Wenn ein Algorithmus aus mehreren Teilen besteht, addiere die Zeitkomplexitäten der einzelnen Teile:

• Regel: Die höchste Zeitkomplexität dominiert.

Beispiel:

def example_function(arr):
    for i in range(len(arr)):  # O(n)
        print(i)
    for j in range(len(arr)**2):  # O(n^2)
        print(j)

• Die Zeitkomplexität für die erste Schleife ist ( 4. Big O(n) ) und für die zweite Schleife ( O(n^2) ).
• Gesamtzeitkomplexität: ( 4. Big O(n) + O(n^2) = O(n^2) )

Fazit

Die Analyse der Zeitkomplexität ist ein entscheidender Schritt, um die Effizienz eines Algorithmus zu verstehen. Mit den beschriebenen Schritten, Regeln und dem Beispiel kannst du die Laufzeit von Algorithmen effektiv bewerten und vergleichen.