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
Top comments (0)