Wie kann man die asymptotische Komplexität von Teilen und Erobern von Algorithmen abschätzen?
Die asymptotische Komplexität von dividieren und erobern Algorithmen kann mit Hilfe eines Mastertheorems geschätzt werden. Der Mastertheorem bietet eine Möglichkeit, die Laufzeit von dividieren und zu erobern Algorithmen, die Algorithmen sind, die ein Problem lösen, indem sie es in Subprobleme, die Subprobleme rekursiv lösen, und dann die Lösungen der Subprobleme kombinieren, um das ursprüngliche Problem zu lösen. Der Mastertheorem besagt, dass, wenn ein dividieren und erobern Algorithmus in Form einer Rezidivbeziehung der Form: T(n) = aT(n/b) + f(n) wo n die Größe des Problems ist, a ist die Anzahl der Subprobleme, b ist der Faktor, um den die Größe der Subprobleme reduziert wird, und f(n) ist eine Funktion, die die Kosten für die Teilung des Problems und die Kombination der Lösungen darstellt, dann die asymptotische Komplexität des Algorithmus wird durch gegeben: T(n) = O(n^d log n)