Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Welche Zeitkomplexität hat die Tiefensuche auf einem Graphen, der als Adjazenzlisten gespeichert ist?

1. AO(V²)
2. BO(V + E)
3. CO(V × E)
4. DO(E log V)

Welche Zeitkomplexität hat die binäre Suche in einem sortierten Array?

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

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)

Welche Zeitkomplexität hat die Multiplikation zweier n × n-Matrizen mit der üblichen dreifachen Schleife?

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

Wie viele Vergleiche braucht die binäre Suche im Worst Case ungefähr bei einem sortierten Array mit 1,000,000 Elementen?

1. AEtwa 20
2. BEtwa 500,000
3. CEtwa 1,000
4. DEtwa 100

Dynamische Programmierung ist nützlich, wenn ein Problem Folgendes aufweist:

1. AÜberhaupt keine Teilprobleme, sodass es in einem Schritt lösbar ist
2. BEine einzige Schleife
3. CNur zufällige Eingaben
4. DÜberlappende Teilprobleme und optimale Teilstruktur

Warum erreicht die binäre Suche auf einer einfach verketteten Liste keine Laufzeit von O(log n)?

1. AVerkettete Listen können nicht sortiert werden
2. BDas Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt
3. CDie binäre Suche braucht mindestens doppelt so viel Speicher
4. DVergleiche auf Knoten verketteter Listen sind langsamer

Liegt 2²ⁿ in O(2ⁿ)?

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