Konzepte und Analyse

Question 1

Rekursion

Answer 1

Funktionsaufruf derselben Funktion innerhalb der Funktion.

Beispiel: Fakultät

int fact(int n) {
if (n < 2) return 1;
return n * fact(n-1);
}

Question 2

Aufwandskalkulation

Answer 2

• Aufwand A;
• Problemgröße n;
• Komplexität: A = A(n)
• Ordnungsfunktion A = O(f (n)) (asymptotisch für große n)

Typische Ordnungsfunktionen – Landau-Notation:
- A = O(1)
- A = O(log n)
- A = O(n)
- A = O(n log n)
- A = O(n^2)
- A = O(2^n) (schwierige Probleme)

Question 3

Ordnungsfunktionen - Rechenregeln

Answer 3

• O(c n) = O(n)
• O(n + c) = O(n)
• O(n + log n) = O(n)
• O(n^2+ n) = O(n^2)
• O(b^n + n^c) = O(b^n)
• O(n! + n^c) = O(n!)