Dein Lernbereich wird geladen
App wird gestartet …
Dein Lernbereich wird geladen
App wird gestartet …
Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
n Problemgröße; a Anzahl Teilprobleme; b Reduktionsfaktor; T und f Aufwandseinheiten
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Gesamtaufwand für ein Problem der Größe n | Operationen | |
| Anzahl rekursiver Teilaufrufe | dimensionslos | |
| Faktor, um den sich die Problemgröße pro Ebene verkleinert | dimensionslos, b>1 | |
| Nichtrekursive Arbeit eines Aufrufs der Größe n | Operationen |
T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1)Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Master-Theorem vergleicht f(n) mit n^(log_b a), ist aber nicht auf jede Rekurrenz anwendbar. Unterschiedliche Teilproblemgrößen, mehrere Rekurrenztypen oder unregelmäßige Aufteilung können andere Methoden erfordern. T zählt ein festgelegtes Rechenmodell, keine reale Sekundenzeit.
Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Master-Theorem vergleicht f(n) mit n^(log_b a), ist aber nicht auf jede Rekurrenz anwendbar. Unterschiedliche Teilproblemgrößen, mehrere Rekurrenztypen oder unregelmäßige Aufteilung können andere Methoden erfordern. T zählt ein festgelegtes Rechenmodell, keine reale Sekundenzeit.
Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt.
Grundbeziehung
Die Gleichung beschreibt die Grundbeziehung innerhalb ihres angegebenen Gültigkeitsbereichs.
Erkläre am Beispiel zu Teile-und-herrsche-Laufzeitrekurrenz, welche Eingabegrößen zur gesuchten Ausgabe führen.
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Die Beziehung ohne ihre angegebenen Voraussetzungen auf einen anderen Fall übertragen.
Prüfe vor dem Einsetzen den Gültigkeitsbereich: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das.
Formelcluster
Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt.
Für MergeSort gilt T(n)=2T(n/2)+cn und T(1)=Θ(1). Hier sind a=2, b=2 und f(n)=cn; über die Ebenen summiert sich der Aufwand zu Θ(n log2 n).
Rekursive Algorithmen analysieren, Rekursionsebenen sichtbar machen und Aufwand mit iterativen Alternativen vergleichen.
Eine typische Aufgabe Schritt für Schritt: Teile-und-herrsche-Laufzeitrekurrenz (T(n) = aT(n/b) + f(n)).
Aufgabe
Erkläre am Beispiel zu Teile-und-herrsche-Laufzeitrekurrenz, welche Eingabegrößen zur gesuchten Ausgabe führen.
Rechenweg
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Die Beziehung T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1) fasst Eine Rekurrenz modelliert rekursive Algorithmen, indem sie Teilprobleme und zusätzliche Arbeit pro Aufruf beschreibt. zusammen. Lies sie als Modell für klar definierte Größen, nicht als automatische Aussage über jede reale Situation. Im Beispiel Für MergeSort gilt T(n)=2T(n/2)+cn und T(1)=Θ(1). Hier sind a=2, b=2 und f(n)=cn; über die Ebenen summiert sich der Aufwand zu Θ(n log2 n). werden die Symbole mit konkreten Werten verbunden und das Ergebnis wird fachlich interpretiert. Gültigkeitsgrenze: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Quelle: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Schreibe zuerst die gesuchte Größe und alle gegebenen Werte mit ihren Bezeichnungen auf. Setze sie in T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1) ein und prüfe, ob die Einheiten zusammenpassen. Das Beispiel Für MergeSort gilt T(n)=2T(n/2)+cn und T(1)=Θ(1). Hier sind a=2, b=2 und f(n)=cn; über die Ebenen summiert sich der Aufwand zu Θ(n log2 n). liefert eine Rechenprobe: Werte Formel und Ergebnis müssen dieselbe Größenordnung und Bedeutung ergeben; runde erst am Ende. Gültigkeitsgrenze: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Quelle: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Die Formel gilt nur, wenn die Größen so definiert sind wie in der Quelle und im Hintergrundtext. Prüfe insbesondere Randfälle, Messbedingungen und ob ein Näherungszeichen statt Gleichheit gemeint ist. Ein formal korrektes Einsetzen kann trotzdem fachlich falsch sein, wenn diese Voraussetzungen verletzt werden oder die betrachtete Population beziehungsweise Systemgrenze wechselt. Gültigkeitsgrenze: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Quelle: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Die angegebene Einheit lautet: n Problemgröße; a Anzahl Teilprobleme; b Reduktionsfaktor; T und f Aufwandseinheiten. Vor dem Einsetzen müssen alle Werte auf ein konsistentes Einheitensystem gebracht werden; Anzahlen, Prozentangaben und dimensionslose Verhältnisse sind dabei nicht austauschbar. Die Variablenliste benennt die Rolle jedes Symbols. Einheitenkontrolle erkennt viele Fehler, ersetzt aber nicht die Prüfung, ob die Formelannahmen erfüllt sind. Gültigkeitsgrenze: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Quelle: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Ein Vergleich hilft, wenn beide Größen dieselbe Aufgabe beantworten, aber unterschiedliche Eigenschaften betonen. Berichte Definition, Eingabedaten, Schwelle oder Aggregation zusammen mit dem Zahlenwert. Die Quelle MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”. stützt die hier verwendete Definition; bei anderen Konventionen können Ergebnisse abweichen. Verwende die Kennzahl deshalb passend zum konkreten Lern- oder Analyseziel. Gültigkeitsgrenze: Die Form T(n)=aT(n/b)+f(n) beschreibt regelmäßige Teile-und-herrsche-Verfahren mit a gleich großen Teilproblemen. Sie braucht einen Basisfall und meist eine Annahme, dass n durch b teilbar ist oder geeignet gerundet wird. Das Quelle: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Teile-und-herrsche-Laufzeitrekurrenz":
Frage (Vorderseite)
Welche Formel beschreibt Teile-und-herrsche-Laufzeitrekurrenz?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei T(n) = aT(n/b) + f(n)?
Antwort in deinem Set
+ 8 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 10 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Erstelle ein kuratiertes FSRS-Prüfungsset für T(n) = aT(n/b) + f(n): Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential