Arbeitsblatt Algorithmen & Komplexität mit Lösungen

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

1. A12 Sekunden
2. B6 Sekunden
3. C9 Sekunden
4. D3 Sekunden

Was ist ein Brute-Force-Algorithmus?

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

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

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

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. BZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen
3. CDie Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
4. DDie Aktivität wählen, die am frühesten beginnt

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

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

Warum wird die Basis eines Logarithmus in der Groß-O-Notation meist weggelassen, wie in O(log n)?

1. ALogarithmen werden immer auf ganze Zahlen gerundet
2. BDie Basis spielt nur für kleine n eine Rolle
3. CAlle Logarithmen in der Informatik haben die Basis 10, die Basis ist also implizit
4. DLogarithmen zu verschiedenen Basen unterscheiden sich nur um einen konstanten Faktor

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

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

Liegt 2²ⁿ in O(2ⁿ)?

1. ANein, denn 2²ⁿ wächst langsamer als 2ⁿ
2. BJa, denn beide sind exponentiell
3. CJa, denn konstante Faktoren im Exponenten werden in der Groß-O-Notation immer ignoriert
4. DNein, denn 2²ⁿ = 4ⁿ und 4ⁿ / 2ⁿ = 2ⁿ wächst unbeschränkt