Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Welche Zeitkomplexität hat Insertionsort im Worst Case?

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

Welche Komplexitätsklasse wächst für große n am schnellsten?

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

Was ist Rekursion?

1. AEine Schleife, die nie endet
2. BEin Sortierverfahren
3. CEine Art von Datenstruktur
4. DEine Funktion, die sich selbst mit kleineren Eingaben aufruft

Was misst die amortisierte Analyse?

1. ADie Kosten eines Algorithmus bei der besten Eingabe
2. BDie Kosten der einzelnen teuersten Operation irgendwo in der Folge
3. CDie durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
4. DDie erwarteten Kosten über zufällige Eingaben

Welche Zeitkomplexität hat: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Welche Zeitkomplexität hat der übliche Algorithmus der dynamischen Programmierung für die längste gemeinsame Teilfolge zweier Zeichenketten der Längen m und n?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Wie erkennt der Bellman-Ford-Algorithmus einen vom Startknoten erreichbaren Kreis mit negativem Gewicht?

1. AEr prüft, ob irgendeine Kante ein negatives Gewicht hat
2. BEr zählt die Kreise mit einer Tiefensuche
3. CEr führt den Dijkstra-Algorithmus zweimal aus und vergleicht die beiden Distanzergebnisse
4. DNach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt

Liegt 2²ⁿ in O(2ⁿ)?

1. AJa, denn beide sind exponentiell
2. BNein, denn 2²ⁿ = 4ⁿ und 4ⁿ / 2ⁿ = 2ⁿ wächst unbeschränkt
3. CJa, denn konstante Faktoren im Exponenten werden in der Groß-O-Notation immer ignoriert
4. DNein, denn 2²ⁿ wächst langsamer als 2ⁿ