Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Welche Zeitkomplexität hat die Tiefensuche auf einem Graphen, der als Adjazenzlisten gespeichert ist?

1. AO(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V × E)

Welche Zeitkomplexität hat Mergesort im Worst Case?

1. AO(log n)
2. BO(n log n)
3. CO(n²)
4. DO(n)

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

1. A8 Sekunden
2. B4 Sekunden
3. C1 Sekunde
4. D2 Sekunden

In einem sortierten Array suchst du zwei Elemente mit einer Zielsumme, indem du von jedem Ende einen Zeiger nach innen bewegst. Welche Zeitkomplexität hat das?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(n²)

Die Zeitkomplexität des naiven rekursiven Fibonacci (fib(n) = fib(n−1) + fib(n−2)) ist:

1. AExponentiell
2. BKonstant
3. CLinear
4. DLogarithmisch

Warum wird die Basis eines Logarithmus in der Groß-O-Notation meist weggelassen, wie in O(log n)?

1. ADie Basis spielt nur für kleine n eine Rolle
2. BLogarithmen werden immer auf ganze Zahlen gerundet
3. CLogarithmen zu verschiedenen Basen unterscheiden sich nur um einen konstanten Faktor
4. DAlle Logarithmen in der Informatik haben die Basis 10, die Basis ist also implizit

Nach dem Master-Theorem hat T(n) = 8T(n/2) + O(n²) die Lösung:

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n log n)

Die Karatsuba-Multiplikation erfüllt T(n) = 3T(n/2) + O(n). Was ist die Lösung?

1. AΘ(n³)
2. BΘ(n^{log₂ 3}), etwa n^1,585
3. CΘ(n²)
4. DΘ(n log n)