Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Welche Zeitkomplexität hat Mergesort im Worst Case?

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

Welche Zeitkomplexität hat das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

Wie viel zusätzlichen Speicher braucht ein üblicher arraybasierter Mergesort?

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

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

1. AMergesort hat keine rekursive Struktur
2. BSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
3. CDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
4. DMergesort ist bereits O(n)

Was ist die Lösung der Rekursionsgleichung T(n) = 2T(n/2) + O(1)?

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

Die Breitensuche (BFS) auf einem ungewichteten Graphen findet:

1. AEine topologische Sortierung in allen Graphen
2. BDen minimalen Spannbaum
3. CKürzeste Wege in Graphen mit negativen Kantengewichten
4. DKürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten

Insertionsort läuft bei sortierter Eingabe in O(n). Widerspricht das der unteren Schranke Ω(n log n) für vergleichsbasiertes Sortieren?

1. AJa, aber nur für Arrays mit weniger als 100 Elementen
2. BJa, die untere Schranke ist also falsch
3. CNein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe
4. DNein, weil Insertionsort kein vergleichsbasiertes Sortierverfahren ist

Warum ist eine Suche in einer Hashtabelle im Durchschnitt O(1), im Worst Case aber O(n)?

1. AViele Schlüssel können im selben Bucket kollidieren
2. BHashfunktionen sind langsam
3. CArrays haben O(n) Zugriffszeit
4. DSchlüssel müssen zuerst sortiert werden