Arbeitsblatt Algorithmen & Komplexität mit Lösungen

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

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

Ein Algorithmus mit zwei verschachtelten Schleifen, die jeweils n-mal durchlaufen werden, hat typischerweise welche Komplexität?

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

Welche dieser Laufzeiten ist polynomiell?

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

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

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

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

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

Welche Greedy-Regel liefert beim Aktivitätsauswahlproblem immer eine maximale Anzahl sich nicht überschneidender Aktivitäten?

1. AZuerst die kürzeste Aktivität wählen
2. BDie Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
3. CDie Aktivität wählen, die am frühesten beginnt
4. DZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen

Welche Zeitkomplexität hat der Aufbau eines binären Heaps aus n unsortierten Elementen mit der Bottom-up-Methode?

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

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

1. AImmer das erste Element wählen
2. BRekursion nur auf der linken Seite verwenden
3. CDen Pivot gleichverteilt zufällig wählen
4. DDie Eingabe vor dem Quicksort sortieren