Big O

#code/algorithmus #finished

Notation in der Informatik, die verwendet wird, um die Effizienz von Algorithmen zu beschreiben, insbesondere in Bezug auf ihre Laufzeit oder ihren Speicherbedarf, wenn die Größe der Eingabe wächst.

Es bietet eine Möglichkeit, die Worst-Case-Komplexität eines Algorithmus in Bezug auf die Eingabemenge zu bewerten.

Es gibt insgesamt 9 Möglichkeiten. Diese sind:

Bsp

Mit diesem Code kannst du herausfinden, um welche Zeitkomplexität es sich handelt. In der example_function solltest du die Funktion einsetzen, deren Zeitkomplexität du ermitteln möchtest.

import time
import matplotlib.pyplot as plt

def example_function(n):
   # Beispielcode mit O(n) Zeitkomplexität
   return sum(range(n))

sizes = []
times = []

for n in range(1, 1001, 100):  # Teste von 1 bis 1000, in Schritten von 100
   start_time = time.time()
   example_function(n)
   end_time = time.time()
   
   sizes.append(n)
   times.append(end_time - start_time)

# Diagramm erstellen
plt.plot(sizes, times, marker='o')
plt.title('Laufzeit der Funktion')
plt.xlabel('Eingabegröße (n)')
plt.ylabel('Zeit (in Sekunden)')
plt.grid()
plt.show()

Zeitkomplexität analysieren