Veröffentlicht · wird verbessert
Algorithm
Mit der O-Notation analysieren, wie Laufzeit und Speicherbedarf eines Algorithmus mit der Eingabegröße wachsen, und die Analyse durch Messen prüfen.
Die Komplexitätsanalyse beschreibt, wie Zeit- und Speicherbedarf eines Algorithmus wachsen, wenn die Eingabe größer wird. Statt Sekunden, die von Hardware und Sprache abhängen, zählt sie elementare Operationen als Funktion der Eingabegröße n und behält nur den dominierenden Term. Das Ergebnis wird in asymptotischer Notation angegeben: Groß-O für eine obere Schranke, Omega für eine untere und Theta für eine scharfe Schranke.
Sie ist wichtig, weil bei wachsenden Datenmengen der Unterschied zwischen Wachstumsraten jeden konstanten Faktor übertrifft. Eine O(n²)-Routine, die bei tausend Elementen problemlos läuft, kann bei einer Million Stunden brauchen, während eine O(n log n)-Variante in Sekunden fertig ist. Mit Komplexität wählt man Datenstrukturen, liest die Eingabegrenzen einer Programmieraufgabe, findet versteckte Kosten im Code-Review und schätzt ab, ob ein System skaliert.
Beginnen Sie damit, Operationen in einfachen Schleifen zu zählen, und lernen Sie die typischen Klassen: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) und O(n!). Danach folgen bester, mittlerer und schlechtester Fall, amortisierte Analyse, Platzkomplexität und das Lösen von Rekurrenzen mit dem Master-Theorem. Prüfen Sie Ihre Überlegungen dabei immer mit einem Verdopplungsexperiment: Laufzeit bei n und 2n messen und das Verhältnis vergleichen.
O, Ω und Θ geben obere, untere und scharfe Schranken für das Wachstum an und ignorieren Konstanten und Terme niedrigerer Ordnung.
Kosten aufeinanderfolgender Blöcke werden addiert, verschachtelte Schleifen multipliziert, und wer das Problem in jedem Schritt halbiert, landet bei einem Logarithmus.
Mittelt die Kosten über eine ganze Folge von Operationen. Deshalb ist das Anhängen an ein dynamisches Array O(1), obwohl gelegentlich alles kopiert wird.
Zusätzlicher Speicher und Rekursionstiefe zählen ebenfalls, und das Master-Theorem löst Rekurrenzen von Teile-und-herrsche-Verfahren.
Das Skript löst dasselbe Problem auf zwei Arten: alle Paare prüfen oder in einem Durchlauf bereits gesehene Werte in einem Dictionary merken. Misst man beide mit timeit bei n = 500, 1.000 und 2.000, wird die quadratische Version bei jeder Verdopplung etwa viermal und die lineare etwa doppelt so langsam.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Komplexitätsanalyse.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Komplexitätsanalyse aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.