Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Was ist ein Brute-Force-Algorithmus?

1. AEiner, der auf vielen Prozessoren läuft
2. BEiner, der immer Rekursion verwendet
3. CEiner, der eine Antwort zufällig rät
4. DEiner, der alle möglichen Lösungskandidaten ausprobiert

Die Platzkomplexität misst:

1. ADen Festplattenplatz der Programmdatei nach dem Kompilieren
2. BDie Anzahl der Codezeilen
3. CDie physische Größe des Computers
4. DDie Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt

Die Laufzeit eines Algorithmus ist O(n). Wie nennt man dieses Wachstum?

1. AQuadratisch
2. BLogarithmisch
3. CKonstant
4. DLinear

Ein Greedy-Algorithmus:

1. ALiefert immer die optimale Lösung
2. BTrifft in jedem Schritt die lokal beste Wahl
3. CProbiert jede mögliche Lösung aus
4. DVerwendet ausschließlich Rekursion

Warum wechseln viele Sortierroutinen in Bibliotheken bei sehr kleinen Teilarrays zu Insertionsort?

1. AInsertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
2. BInsertionsort braucht bei großen Eingaben weniger Speicher als jeder andere Sortieralgorithmus
3. CInsertionsort ist im Worst Case O(n log n)
4. DRekursive Algorithmen können Arrays mit weniger als 10 Elementen nicht verarbeiten

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(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

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

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

Wie hoch sind die amortisierten Kosten für das Inkrementieren eines Binärzählers, wenn ein einzelnes Inkrement viele Bits umschalten kann?

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