Das Mastertheorem
Вставка
- Опубліковано 7 лип 2024
- Mit dem Mastertheorem lassen sich Laufzeiten von Teilen-und-Herrschen-Algorithmen bestimmen, bei denen die Eingabe in eine feste Zahl (fast) gleich großer Teile aufgeteilt wird. Dabei gibt es drei Fälle zu unterscheiden, die man sich anhand einer "Chef vs. Mitarbeiter"-Regel merken kann:
* 1. Der Chef arbeitet mehr als seine direkten Mitarbeiter zusammen. Dann wird die Laufzeit von der Arbeitzeit des Chefs bestimmt.
* 2. Der Chef arbeitet weniger als seine direkten Mitarbeiter zusammen. Dann wird die Laufzeit von der Zahl der Blätter des Aufrufbaums bestimmt.
* 3. Der Chef arbeitet genauso viel wie seine direkten Mitarbeiter zusammen: Nun kommt die Höhe des Aufrufbaums mit ins Spiel; diese spendiert der Gesamtlaufzeit einen zusätzlichen log-Faktor.
00:00 - Intro
00:19 - Teilen und Herrschen (siehe auch • Teilen und Herrschen )
04:04 - Rekursionsgleichung für die Laufzeit
15:18 - Fall 1: Chef arbeitet mehr
21:52 - Rechenbeispiel für Fall 1
22:58 - Fall 2: Chef arbeitet weniger
28:16 - Tiefe des Aufrufbaums
30:47 - Rechenbeispiel für Fall 2
31:51 - Fall 3: Cheff arbeitet gleich viel
33:18 - Rechenbeispiel für Fall 3
- Einführung Teilen und Herrschen: • Teilen und Herrschen
- Beispiel für Fall 3: MergeSort: • MergeSort
Bin bei Minuten 7 und hatte schon mehrere Aha-Erlebnisse, obwohl ich das MT schon mehrfach erfolgreich angewendet habe. Super gut!
Sehr hilfreiches Video, vielen Dank für die gute Erklärung, weiter so!
Super verständliches Video! Mehr verstanden als in einem ganzen Semester.. :D
Sie sind echt der Beste!!! Durch Sie verstehe ich auch endlich mal diese komplizierten Formeln, die unser Prof nicht gescheit erklärt! Danke
🙂
Vielen Dank! Das Video hat mir sehr geholfen!
Ich war noch nie so dankbar über ein Lernvideo! Vielen Dank du rettest mich aus der Verzweiflung!
ich war noch nie so dankbar für so ein geniales intro
@@timonschramm6141 ist auch danceable
Super erklärt, vielen Dank!
extrem gute Erklärung! danke dafür, das hat mir sehr weitergeholfen :)
wow, nirgends so eine gute Erklärung gefunden, danke!
sehr gut erklärt, direkt verstanden, merci
geil erklärt! gute dynamik! Vielen Dank!
Sehr gutes Video! Ich wünschte wir hätten so einen Prof.
Vielen Dank!!
sehr gut erklärt! gutes Video!
Danke schön!
War gut erklaert und sinnvoll eingeteilt 👍🏽
Sehr gutes Video!
Sehr gute Videos! Sie sprechen in diversen Videos von einem Buch, haben Sie ein Buch geschrieben über Algorithmen und DS? Wenn es so ist, wie Ihre Videos, dann würde ich es sofort kaufen. Bin noch auf der Suche nach einer guten Lektüre über diese Themen, die sich behandeln. Oder können Sie etwas empfehlen?
Ja, das Buch heißt "Algorithmen und Datenstrukturen für Dummies" und ist im Verlag Wiley-VCH erschienen.
Wie machen Sie das eigentlich, dass Sie so präzise auf etwas zeigen können und es von der Kamera erfasst wird? Danke!
Ich denke er hat schräg rechts von sich einen Bildschirm stehen, auf dem er sich und das Geschriebene sieht, so wie wir es sehen.
@@kritzelbrabp Faszinierend. Würde das auch gerne mal so hinbekommen. Was für ein Tool könnte man da wohl nehmen…
10:02
Von wo kommt das ..+a ?
Sollte es nicht so sein:
T(n) = a^2 * T(n/b^2) + f(n/b) + f(n)
Ich würde gerne die Berechnung sehen
Im Ausdruck T(n) = a* T(n/b) + f(n) möchte ich T(n/b) durch a*T(n/b^2) + f(n/b) ersetzen. Dieser letzte Ausdruck ist also eine Summe von a*T(n/b^2) und f(n/b), und diese Summe muss ich nun beim Einsetzen mit a multipliziere, d.h. ich muss jeden der beiden Summanden mit a multiplizieren. Das nennt man "Ausmultiplizieren" und ist das Gegenteil vom "Ausklammern" (Siehe z.B. de.wikipedia.org/wiki/Distributivgesetz ). Ich habe mir erlaubt, diesen Zwischenschritt wegzulassen und einfach das Ergebnis hinzuschreiben.
@@Gogol-Doering danke das habe ich übersehen
Ich bin so froh, dass ich das Video doch aufgerufen habe. Ich dachte zuerst, dass es sich um ein Video für Studis handelt, die ihre Master-Thesis entwickeln sollen. 😂😂😂😂
Btw, wie wird zukünftig KI/LLMs in eurem Bereich integriert werden? Meine Studis sind aktiv dazu aufgerufen, Prompts zu entwickeln, die ihnen zum Erreichen der Ziele dienlich sein können. zB Entwicklung von Stundenbildern, Arbeitsunterlagen, Aufgabenstellungen etc.
Ich überlege tatsächlich gerade, ob ich zum Thema AI und insbesondere zu ChatGPT ein Video aufnehme. Allerdings sehe ich diese Sachen recht kritisch. Ich bin wohl einer der ganz wenigen Informatiker, die AI doof finden. 😉
@@Gogol-Doering , cool! Ich werde das Video definitiv liken, teilen und kommentieren! 🙌
macher
Sehr gute Video!