Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Mastertheorem
Rekurrenzen Algorithmen der Informatik Ableitung der untersten Schranke von Sortierverfahren n·log(n)
Unterabschnitte

Mastertheorem

Übersicht


\begin{displaymath}T(n)=\Bigl\{\begin{array}{ll} O(1)&falls\,n=1\\ a*T(\frac{n}{b})+c*n&falls\,n=b^{k}>1\\ \end{array}\end{displaymath}

1.Fall: $a<b:T(n)=\Theta(n)$
2.Fall: $a=b: T(n)=\Theta(n*log(n))$
3.Fall: $a>b: T(n)=\Theta (n^{k})\,mit\,k=log_{b}(a)$

Verständnis des Beweises

Das Mastertheorem sind im Prinzip Regeln, die aussagen, welches Laufzeitverhalten der Algorithmus hat. Die Laufzeit wird abhänging von der Größe der einzelnen Teilprobleme, der Anzahl der entstandenen Teilprobleme und der Rechenzeit für die Erstellung bzw. Zusammenführung dieser Teilprobleme bestimmt.
  • Dabei ist klar, daß wenn die Teilprobleme summiert kleiner sind als das Orignialproblem und die Erstellung der Teilprobleme auch nur linare Zeit beansprucht, der ganze Algorithmus in linearer Zeit ausgeführt werden kann.
  • Wenn die Größe der Teilprobeme genau der Größe des Orignialproblems ist und des weiteren linearer Platz gebraucht wird, um diese Teilprobleme zu erstellen, benötigen wird $\Theta(n\log{n})$ Zeit.
  • Werden die einzelnen Teilprobleme in der Summe größer, als das Orignalproblem ist klar, daß wir noch mehr Laufzeit benötigen.


Rekurrenzen Algorithmen der Informatik Ableitung der untersten Schranke von Sortierverfahren n·log(n)