Arbeitsblatt Algorithmen & Komplexität mit Lösungen

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

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

Ein O(n)-Algorithmus braucht für n = 1 Million 3 Sekunden. Wie lange braucht er etwa für n = 2 Millionen?

1. A9 Sekunden
2. B3 Sekunden
3. C12 Sekunden
4. D6 Sekunden

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

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

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

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

Welche Aussage über eine rekursive Funktion ohne erreichbaren Basisfall ist richtig?

1. ASie gibt automatisch 0 zurück
2. BSie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
3. CSie läuft in O(1) Zeit
4. DDer Compiler wandelt sie immer in eine Schleife um, die sicher endet

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

Nach dem Master-Theorem hat T(n) = 8T(n/2) + O(n²) die Lösung:

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n² log n)