Komplexität von Algorythmen

Question 1

Wie misst man Laufzeitbedarf?

Answer 1

gute Lösung:
man zählt Einzelschritte des Algorithms, bzw ausgeführte Anweisungen

ungeeignete Lösung:
Ausführzeit messen, da diese immer vom Rechner abhängt

Question 2

O-Notation

Answer 2

f(n) ≤ c · g(n)

Für alle n ≥ n0 existieren eine Konstante c € ℝ+ und ein n0 € ℕ.

Question 3

Komplexitätsklassen

Answer 3

O(1) konstanter Aufwand
O(log n) logarithmischer Aufwand
O(n) linearer Aufwand
O(n · log n) linear-logarithmischer Aufwand
O(n2) quadratischer Aufwand
O(n^k) für k ≥ 1 polynomialer Aufwand
O(k^n) für k > 1 exponentieller Aufwand

Question 4

Bestimmen Sie für diesen Algorithmus den Laufzeitbedarf f(n) (Anzahl Arbeitsschritte) in Abhängigkeit von der Problemgröße n (Feldlänge)!
Zu welcher der in der Vorlesung kennengelernten Komplexitätsklassen gehört der Laufzeitbedarf
dieses Algorithmus? Beweisen Sie Ihre Aussage!

1 public static void sort(int[] array) {
2    for (int i = 0; i < array.length - 1; i++) {
3       // finde minimalen Wert im unsortierten Bereich
4       int min = i;
5       for (int j = i + 1; j < array.length; j++) {
6          if (array[j] < array[min]) {
7             min = j;
8          }
9       }
10      // vertausche Positionen i und min
11       int temp = array[i];
12      array[i] = array[min];
13      array[min] = temp;
14   }
15}

Answer 4

2. ) 2 4 3
3. ) 3
4. ) 4 3 3
5. ) 5
6. ) 2
7. ) 4
8. ) 4
9. ) 3
10. for schleife: (n-1) durchläufe
11. for schleife: (n-1) durchläufe

f(n) = 2 + (n-1)* [ 4+3+3+4+ (n-1)* (3+3+5+2) +3+4+4+3 ]+4

f(n) = 13n^2 + 2n - 9

BEWEIS:
13*n^2 + 2*n - 9   <=  c*n^2
                             <= 13*n^2 + 2*n^2
                               = 15*n^2
->> c = 15

Antwort: Laufzeitkomplexität von O(n^2)