Eigenschaften eines Programms
- Effizienz
- Korrektheit
- Zuverlässigkeit
- Robustheit
Zeitkomplexität: Aufwand an Rechenzeit (in Schritten gemessen)
Unterscheidung:
- worst-case
- best-case
- average-case
Beschreibung:
- exakt: Zählfunktion T: N -> N; n ∈ N
- asymptotisch: Angabe einer Vgl.größe (Komplexitätsklasse)
Speicherplatzkomplexität: Umfang des zu reservierenden Speicherplatzes
Komplexitätsklassen
obere Schranke
O(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≤ c * f(n)}
untere Schranke
Ω(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≥ c * f(n)}
O( 1 ) – konstant
O( log2n ) – logarithmisch – Bsp. binäre Suche
O( n ) – linear – Bsp. sequentielle Suche
O( n * log2n ) – n log n – Bsp. gute Sortierverfahren
O( n² ) – quadratisch
O( n³ ) – kubisch
O( 2^n ) – exponentiell
Faustregeln
- Fallunterscheidung: Kosten der Anweisung + Kosten der teuersten Alternative
- Schleife: Zahl der Durchläufe * Kosten der teuersten Durchführung
- Rekursion: Anzahl der Aufrufe * Kosten der teuersten Durchführung
- Vergleich versch. Operationen: Kosten der einzelnen Operationen bestimmen