Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Welche Laufzeit hat Countingsort für n ganze Zahlen im Bereich 0 bis k?

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

Was bedeutet es, wenn eine Operation in O(1) Zeit läuft?

1. ASie verarbeitet genau ein Element pro Sekunde Laufzeit
2. BIhre Laufzeit wächst nicht mit der Eingabegröße
3. CSie dauert immer genau eine Sekunde
4. DSie kann nur einmal ausgeführt werden

Welche Zeitkomplexität hat die lineare Suche in einem unsortierten Array mit n Elementen (Worst Case)?

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

Eine Funktion führt eine Schleife mit n Iterationen und danach, getrennt davon, eine weitere Schleife mit n Iterationen aus. Welche Zeitkomplexität hat sie?

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

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)

Wie viel Stack-Speicher braucht eine einfache rekursive Fakultätsfunktion fact(n) = n × fact(n − 1)?

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

Das 0/1-Rucksackproblem benötigt mit dynamischer Programmierung O(nW) Zeit. Warum nennt man das pseudopolynomiell?

1. AWeil der Algorithmus randomisiert ist und seine Laufzeit je nach Eingabe schwankt
2. BWeil n immer klein ist
3. CWeil er nur für W = 0 funktioniert
4. DW ist eine Zahl, daher ist die Laufzeit exponentiell in der Anzahl der Bits, mit denen W geschrieben wird

Welche Technik liefert für Quicksort bei jeder Eingabe eine erwartete Laufzeit von O(n log n)?

1. ARekursion nur auf der linken Seite verwenden
2. BDie Eingabe vor dem Quicksort sortieren
3. CImmer das erste Element wählen
4. DDen Pivot gleichverteilt zufällig wählen