DEV Community

Cover image for Komlexität von Algorithmen
Anne Quinkenstein
Anne Quinkenstein

Posted on • Updated on

Komlexität von Algorithmen

Was ist ein Algorithmus?

EVA Prinzip

Grundprobleme

  • Berechenbarkeit
  • Korrektheit
  • Terminiertheit
  • Komplexität (Wie lange?)

Eigenschaften

  • Determiniertheit (Kommt dasselbe bei dem selben Input raus?)
  • Determinismus (Gibt es immer eindeutig eine nächste Anweisung?)
  • Finitheit (gibt es ein Ende?)
  • Effektivität (Ist der Effekt jeder Anweisung klar?)

Komplextität eines Algorithmus

O-NOTATION

•Komplexitätsklassen werden in O-Notation angegeben -> f ∈ O(g)
•Bei dieser Angabe gilt: "g dominiert f"
•f ∈ O(g) ⟷ es gibt n0, c ∈ ℕ, so dass f(n) ≤ c × g(n) für alle n ≥ n0

Häufig benutzte Komplexitätsklassen

•O(log(n))
•O(n log(n))
•O(n)
•O(n2)
•O(2n)

Image description

konstant: O(1);
logarithmisch: O(log n), O(log² n)
linar: O(n)
linar-logarithmisch: O(log n * n)
quadratisch: o(n²)
kubisch: O(n³)
exponentiell: O(2hochn)
falkutlät: O(n!)

Analysen von Programmen
wenn sich mit jeden Schritt das Problem halbiert: logarithmische Komplexität
schleife in schleifen: quadratische

Top comments (0)