Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Kostenloses Arbeitsblatt Algorithmen & Komplexität zum Ausdrucken: 8 Aufgaben von leicht bis Prüfungsniveau, mit Lösungsschlüssel. Drucke es aus oder speichere es als PDF.

Neues ArbeitsblattOnline mit Tipps üben

Für Lehrkräfte: kostenlos ausdrucken, kopieren und im Unterricht verwenden. Jedes neue Arbeitsblatt hat neue Werte und einen eigenen Lösungsschlüssel. Über einen Link zu ExamProblems auf Ihrer Kursseite freuen wir uns.

Name: ____________________   Datum: ____________

1.Leicht

Welche Komplexitätsklasse wächst für große n am schnellsten?

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

Wie lautet die Groß-O-Klasse von 3n² + 5n + 2?

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

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)
  4. DO(n log n)
4.Mittel

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 ist im Worst Case O(n log n)
  3. CInsertionsort braucht bei großen Eingaben weniger Speicher als jeder andere Sortieralgorithmus
  4. DRekursive Algorithmen können Arrays mit weniger als 10 Elementen nicht verarbeiten
5.Mittel

Was ist die Lösung der Rekursionsgleichung T(n) = T(n − 1) + O(n)?

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

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

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

Warum braucht jede vergleichsbasierte Suche in einem sortierten Array im Worst Case Ω(log n) Vergleiche?

  1. ADie binäre Suche ist der einzig mögliche Algorithmus und braucht log₂ n Vergleiche
  2. BJeder Vergleich braucht logarithmische Zeit
  3. CEin Entscheidungsbaum mit n möglichen Ergebnissen muss mindestens die Tiefe log₂ n haben
  4. DJedes Element muss mindestens einmal verglichen werden
8.Schwer

Welche Definition der Klasse NP ist richtig?

  1. AProbleme, die nicht in polynomieller Zeit gelöst werden können
  2. BProbleme, die nicht polynomiell sind
  3. CEntscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können
  4. DProbleme, die kein Algorithmus lösen kann

Lösungsschlüssel

  1. 1. C · O(2ⁿ)
  2. 2. B · O(n²)
  3. 3. C · O(n)
  4. 4. A · Insertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  5. 5. A · O(n²)
  6. 6. D · O(n³)
  7. 7. C · Ein Entscheidungsbaum mit n möglichen Ergebnissen muss mindestens die Tiefe log₂ n haben
  8. 8. C · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können

Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.