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

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

  1. A1 Sekunde
  2. B2 Sekunden
  3. C4 Sekunden
  4. D8 Sekunden
2.Leicht

Welche Zeitkomplexität hat Mergesort im Worst Case?

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

Ein Algorithmus mit zwei verschachtelten Schleifen, die jeweils n-mal durchlaufen werden, hat typischerweise welche Komplexität?

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

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

  1. AMergesort hat keine rekursive Struktur
  2. BSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  3. CMergesort ist bereits O(n)
  4. DDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
5.Mittel

Die Zeitkomplexität des naiven rekursiven Fibonacci (fib(n) = fib(n−1) + fib(n−2)) ist:

  1. ALinear
  2. BExponentiell
  3. CLogarithmisch
  4. DKonstant
6.Mittel

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

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

Welche Schranke ist für log(n!) richtig?

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

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

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

Lösungsschlüssel

  1. 1. C · 4 Sekunden
  2. 2. D · O(n log n)
  3. 3. B · O(n²)
  4. 4. B · Seine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  5. 5. B · Exponentiell
  6. 6. B · O(n)
  7. 7. C · Θ(n log n)
  8. 8. B · Das Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt

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