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)

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