Diskussion:Master-Theorem

Irgendwie anders

Ich kenne das Master-Theorem aus "Algorithmik" von Uwe Schöning deutlich anders und einfacher!

Hier geht man von folgender Formel aus: $T(n)=\sum \limits _{i=1}^{m}{T(a_{i}n)+\Theta (n^{k})}$. Wenn man aber sowas wie $T(n)=2*{T(a_{i}n)+\Theta (n^{k})}$ hat, dann ergibt sich die oben genannte Formel einfach zu $T(n)={T(a_{i}n)+T(a_{i}n)+\Theta (n^{k})}$.

$T(n)={\begin{cases}\Theta (n^{k}),&{\mbox{wenn }}\sum \limits _{i=1}^{m}\alpha _{i}^{k}<1\\\Theta (n^{k}\log n),&{\mbox{wenn }}\sum \limits _{i=1}^{m}\alpha _{i}^{k}=1\\\Theta (n^{c}),&{\mbox{wenn }}\sum \limits _{i=1}^{m}\alpha _{i}^{k}>1\\\end{cases}}$

Bei Fall 3 kann das c über $\sum \limits _{i=1}^{m}\alpha _{i}^{c}=1$ bestimmt werden. Sind alle $a_{i}$ gleich, dann $c=-{\frac {\log m}{\log \alpha }}$.

---

Die Variante von Schöning ist hier zu finden. http://de.wikipedia.org/wiki/Master-Theorem_(allgemeinere_Form) Allerdings fehlt der Spezialfall, wenn alle $a_{i}$ gleich sind.

Artikel nicht allgemeinverständlich

Der ganze Artikel ist eine einzige Aufzählung von mathematischen Formeln und erklärt überhaupt nichts, noch nicht einmal die Bedeutung bzw. die Bezeichnung der in den Formeln verwendeten Symbole. Es gibt auch keine Links auf verwandte Themen, bei denen das alles evtl. erklärt würde. Dieser Beitrag hätte so noch nicht einmal in einer (guten) Formelsammlung etwas verloren, geschweige denn in einer Enzyklopädie - er gehört also gründlich überarbeitet. --84.152.202.18 23:31, 21. Mai 2005 (CEST)

Mir fehlen u.a. die Erklärung was a,b,n,T,Theta und f(n) sein sollen. Ich kann mir zwar bei einigen Symbolen denken, für was sie stehen sollen, und ich kann annehmen, daß manche andere die gleiche Bedeutung haben sollen wie auf Seiten, die ich über einen bis viele Links erreichen kann, aber es steht eben nicht auf dieser Seite. Die Kommentare zwischen den Formeln kommentieren vor allem die Umformungen und Einsetzunge, erklären aber nicht, warum gerade so umgeformt und eingesetzt wird. Aus der jeweils resultierenden Formel wird kein Fazit gezogen, keine Bedeutung angegeben, es wird nicht auf die Gültigkeit dieser Formeln eingegangen usw. --84.152.202.18 01:36, 22. Mai 2005 (CEST)

Hi! So, hier mal eine kurze Anmerkung von dem der den Artikel erstellt hat ;) Du schreibst dass dir die Erklärung fehlt was Theta O, etc sein sollen. Dies gehört meiner Meinung nach nicht in den Artikel, da es im Artikel O_Notation welcher direkt im ersten Satz verlinkt ist erklärt ist. Zwar sollten -- da stimme ich mit dir überein -- Artikel allgemeinverständlich sein, aber bei Themen die über die Grundlagen hinausgehen kann man IMHO diese nicht immer wieder erwähnen. Die Grundlagen sind wie gesagt in der Einleitung verlinkt. Was a,b, und n sein sollen, wird denke ich klar sobald man sich die Beispiele ansieht. Aber ok, hier könnte man in der Tat hinzuschreiben dass es sich um bestimmte Konstanten handelt. (Später in den Beispielen wird ja deutlich dass irgendwelche Zahlen eingesetzt werden). Aber was meinst du mit Umformungen? Eigentlich habe ich -- so weit ich weiß -- nirgends etwas umgeformt. Die Beispiele sind simples einsetzen um die allgemeine Form mit etwas "Leben" zu füllen. Warum gerade so eingesetzt wird: Weil es ein Beispiel ist. Irgendwelche Werte musste ich ja nehmen ;) Thema "Gültigkeit der Formeln": Hm, stimmt, ein Beweis für die gültigkeit der Formeln fehlt in der Tat. Aber da ich den Beweis momentan nicht aus dem Ärmel schütteln kann werde ich dieses Problem erst einmal auf jemand anderen abwälzen müssen ;) Aber bedenke: Wenn du einen Beweis für die Gültigkeit der Formel einbaust, dann wird der Artikel noch unverständlicher ;) Zum Thema Fazit: Ok, hier kann ich dir bedingt zustimmen. Habe als Fazit nur eine Formel stehen, welche für mich eindeutig genug war. Aber werde das ganze nochmals in einem Deutschen Satz zusammenfassen, und mal versuchen Teile deiner Vorschläge in den Artikel einzubauen. Falls du noch irgendwelche konkreten Probleme mit dem Artikel hast: Immer her damit ;) Regnaron 21:52, 23. Mai 2005 (CEST)

Auch mal senf zugeb: Also meiner Meinung nach ist der Artikel gut gelungen und leicht nachvollziehbar (vor allem wenn es um die Anwendung des Mastertheorems geht...). Zur gültigkeit der Formeln: sie sind gültig wenn anwendbar (sich also der Algorithmus in eine entsprechende Form bringen lässt), ansonsten wären nur noch die Beweise zur gültigkeit anbringbar, was, denke ich, den Rahmen eines solchen Artikels sprengen würde. Wie der Author selbst schon bemerkt hat, sind direkt am Anfang Links auf die Komplexitätstheorie gesetzt, in die dieser Artikel einzuordnen ist. Unter dieser ist auch die O-Notation usw. zu finden. Allenfalls eine kurze Erklärung zur Einteilung in die 3 Fälle könnte erfolgen (bzw der Hinweis, dass und wie sich die Fallluntersheidung während der Anwendung ergibt).Gröbere überarbeitungen sind meiner Meinung nach nicht nötig. Ausserdem ist der Artikel mit "komplexitätstheorie auch korrekt eingeordnet. --Pheredhel 20:41, 13. Jul 2005 (CEST)

Hi! Danke erstmal für die bestätigung meiner Vermutung dass der Artikel doch nicht so unverständlich ist. Dann kann ich den Unverständlichkeitsbaustein ja endlich wieder rausnehmen :) Aber wie meist du das mit "Erklärung zur Einteilung in die drei Fälle?" Ein Fall ist anwendbar wenn die gegebene Formel in der entsprechenden Form ist, oder in die entsprechende Form zu bringen ist. Was schwebte dir denn da als weitergehende Erklärung vor? Regnaron 06:21, 15. Jul 2005 (CEST)

hi leute, also ich muss auch sagen, dass ich den Artikel wirklich gut verstanden hab. Er gibt einblick in die Anwendung des, doch recht schwer zu verstehenden, Master Theorems... Und wer sich schon das MasterTheorem anschaut und keine Ahnung von Landau Notation hat, sollte doch ganz die Klappe halten. Das sind die Basics dafuer, wer die nicht kennt, hat hier noch nichts verloren... und die entsprechende Anmerkung ueber Laufzeit ist sofort im ersten Satz zu finden... also alles in allem gelungener Artikel. Meine Frage dazu ist jetzt lediglich, ob es noch Unterscheidungen zwischen O und o (ebenso Omega und omega) gibt und wie sich diese dann zeigen und warum es genau 3 Faelle gibt. cu and keep on writing ... Milchmann

Danke erst einmal für das Positive Feedback :)

Ist zwar eigentlich die Falsche Stelle um es zu erklären, aber ja, es gibt Unterschiede zwischen O und o. Dieser Unterschied ist aber recht marginal. Wenn du dir die Definition von O anguckst, findest du dort ein $\leq$ Zeichen vor. in o wird das einfach nur durch ein $<$ ersetzt. Bei Omega ist es Analog. Also während das eine die Funktionenklasse der Funktionen ist die schneller oder gleichschnell wachsen, ist das andere die Funktionenklasse der Funktionen die echt schneller wachsen, bzw echt langsamer.

Um wieder zum Artikel zurückzukommen: Warum es genau drei Fälle gibt? Hm, gute Frage. Aber ich denke mal weil man nur für diese drei Fälle den Beweis führen kann das das Master Theorem in dieser Art der Anwendung stimmt, und es eben keine vierte Allgemeingültige Formel gibt. Aber da das Momentan von meiner Seite her selbst nur Spekulationen sind habe nich es nicht in den Artikel eingebaut. Regnaron 22:51, 15. Jul 2005 (CEST)

Hallo, der Artikel ist für mich perfekt formuliert und verständlich, dennoch würde ich gerne wissen, ob nicht noch mehr Einschränkungen für die Funktion f(n) gelten. So wurde an der Universität f(n) wie folgt definiert: "eine auf den exakten Potenzen von b definierte positive funktion". So wäre z.b. das Mastertheorem nicht auf eine Funktion wie $T(n)=36*T(n/6)+n*logn+n$ anwendbar. Kann jemand dazu weiteres Fachwissen beisteuern?

Hi! Auch dir erstmal danke fürs Feedback :) Hm, das Tatsache dass f(n) immer positiv sein muss müsste ich selbst mal nachgucken. Aber momentan wüsste ich nicht wirklich was dagegenspricht. (Mal die Tage wenn der Klausurstress rum ist ein paar Beispiele durchrechnen...) Aber was meinst du mit "auf den exakten Potenzen von b definiert"? Also insbesondere was meinst du mit "exakter Potenz"? Dein Beispiel habe ich mal eben überflogen, aber mir scheint es durchaus in die erste Kategorie von Beispielen zu passen. (hatte aber noch nicht die Zeit das Ergebnis empirisch zu überprüfen) Regnaron 18:21, 19. Jul 2005 (CEST)

Artikel umgeschrieben

Hi! Ich habe alle drei Fälle des Mastertheorems in eine Tabelle gepackt, die für mich viel viel übersichterlicher ist und dadurch verständlicher wirkt. Ich hoffe ihr habt nichts dagegen und seid der gleichen Meinung. Zu der Frage, wie man $T(n)=36*T(n/6)+n*logn+n$ lößt, habe ich einen solchen Typ als "Spezialfall" beschrieben und gezeigt, wie dieser zu lösen ist. (27. Mar 2006)

Hi! Hm, die Idee mit der Tabelle macht das ganze sicherlich schonmal übersichtlicher. Schockt die Oma vielleicht ein bisschen, aber ich glaube das ist bei dem Artikel zu verkraften :-) Zu dem Spezialfall: An sich eine nette Idee, aber man sollte das ganze noch etwas besser einleiten. Habe nämlich bevor ich die Diskussionsseite gelesen habe nicht wirklich verstanden was an genau dieser konkreten Gleichung ein Spezialfall gewesen sein sollte. Vielleicht noch eine kleine Einleitung in den "Spezialfall" aka: Da nicht alle Rekurrenzgleichungen direkt mit dem Master Theorem zu lösen sind, soll hier ein Weg aufgezeigt werden wie man manche von diesen Gleichungen trotzdem mit seiner Hilfe lösen kann. Regnaron 06:50, 27. Mär 2006 (CEST)

Gut.--217.233.179.28 23:59, 27. Mär 2006 (CEST)

Ich habe eben gemerkt, dass mein "Trick" nicht ganz aufgeht. Mein Fehler war, dass ich behauptet habe T₂∈(n³). Richtig ist allerdings T₂∈(n⁴). sorry.--217.233.162.55 14:49, 28. Mär 2006 (CEST)

So. Nun ist der Spezialfall mit einer zusätzlichen Formel korrigiert.--217.233.158.60 01:48, 30. Mär 2006 (CEST)

"Von T(n) unabhängig"

Was soll das "unabhängig in "Ferner bezeichnet f(n) eine von T(n) unabhängige und nicht negative Funktion" bedeuten? Ich habe noch nie was von unabhängigen Funktionen (außer bei Zufallsvariablen in der Stochastik oder im Sinne linearer Unabhängigkeit) gehört. Falls es sich einfach nur um ein Füllwort handelt, sollte man es löschen, da es verwirrend ist, und ansonsten wäre es sinnvoll, auf die Definition verweisen (sie ist mir als Informatikstudent in einem höheren Semester nicht bekannt, und das ganze sollte für Laien verständlich sein). Weiß jemand etwas dazu? 92.226.208.254 19:01, 13. Aug. 2008 (CEST)

Na das soll heißen, dass T in f nicht benutzt wird. --Chricho ¹ 22:56, 12. Okt. 2011 (CEST)

Soetwas wie Unabhängigkeit im mathematischen Sinne ist das natürlich nicht. Stellt man die Formel nach f(n) um, so hat man die Abhängigkeit von f von T. Man sollte besser schreiben: "In der Funktionsvorschrift von f taucht T nicht auf" oder so etwas. (nicht signierter Beitrag von 89.12.39.37 (Diskussion) 11:08, 20. Feb. 2013 (CET))

Fälle

Sollte nicht irgendwo stehen, was die drei Fälle denn bitte sind? --Chricho ¹ 22:55, 12. Okt. 2011 (CEST)

Hauptsatz der Laufzeitfunktionen

Sollte man den Artikel nicht besser auf das deutsche Lemma Hauptsatz der Laufzeitfunktionen verschieben? 92.231.188.246 10:06, 11. Dez. 2011 (CET)

Unterstützt. --78.51.30.2 22:51, 20. Okt. 2015 (CEST)

Rekurrenz

Streng genommen müsste man bei der Rekurrenzgleichung

$T\left(n\right)=a\cdot T\left({\tfrac {n}{b}}\right)+f\left(n\right)$

auch den Rekursionsabschluss erwähnen, also $T\left(n\right)\in {\mathcal {O}}\left(1\right)$ für $n\leq n_{0}$. (Oder in einer der anderen Formulierungen, wie etwa $T\left(n\right)=\mathrm {const.}$ für $n\leq n_{0}$.) Ich weiß nicht, ob diese Gleichung als reine Funktionalgleichung nicht noch andere Lösungen haben kann, die vom Master-Theorem nicht erfasst werden. Spontan fällt mir kein Gegenbeispiel ein. --78.51.72.71 21:09, 17. Feb. 2016 (CET)

Zweiter Fall falsch?

In der Tabelle steht im Moment für den zweiten Fall

$f(n)\in \Theta (n^{\log _{b}{a}})\Rightarrow T(n)\in \Theta (n^{\log _{b}{a}}\cdot \log n)$.

Ich habe in einer Vorlesung aber folgende Form gelernt:

$\exists k\in \mathbb {N} :f(n)\in \Theta (n^{\log _{b}{a}}{\color {blue}\cdot (\log _{2}{n})^{k}})\Rightarrow T(n)\in \Theta (n^{\log _{b}{a}}{\color {blue}\cdot (\log _{2}n)^{k+1}})$

Da ich gerade keine vertrauenswürdige Quelle zur Hand habe, will ich den Artikel nicht ändern. Zumindest die englische Wikipedia ([1]) scheint meinen Verdacht, dass der Artikel so nicht stimmt, zu stützen. Dass dort nicht der logarithmus dualis benutzt wird, ist ja egal, da die Logarithmen sich nur in Konstanten unterscheiden.
())¯_¯_¯_¯_>2 (Diskussion) 14:29, 3. Mär. 2017 (CET)