Mästarsatsen

Från Unix.se, den fria unixresursen.

Mästarsatsen (eng Master theorem) är en sats som enkelt kan ge lösningen till vissa vanliga rekursionsekvationer. Inom datalogin används den ofta för att underlätta det asymptotiska beteendet för dekompositionsalgoritmer.

Sats

Låt <math>\, a \geq 1, b > 1, d > 0 </math>, och låt <math>\, f(n)</math> vara en diskret funktion. Då har rekursionsekvationen <math>\, \begin{cases} T(n) = aT(\frac{n}{b}) + f(n) \\ T(1) = d \end{cases} </math>

den asymptotiska lösningen

• <math>\, T(n) = \Theta (n^{\log_{b} a}) </math>, om <math>\, f(n) \in O(n^{\log_{b} a - \epsilon}) </math> för något <math>\, \epsilon > 0 </math>
• <math>\, T(n) = \Theta (n^{\log_{b} a}\log n) </math>, om <math>\, f(n) \in O(n^{\log_{b} a}) </math>
• <math>\, T(n) = \Theta (f(n)) </math>, om <math>\, f(n) \in \Omega (n^{\log_{b} a + \epsilon}) </math> för något <math>\, \epsilon > 0 </math> och <math>\, af(\frac{n}{b}) \leq cf(n) </math> för någon konstant <math>\, c > 0</math>, för alla tillräckligt stora <math>\,n</math>

Notera att för vissa <math>\,T(n)</math> så ger satsen ingen information alls (dvs det är inte alltid så att precis en av de tre ovanstående är fallet).

Exempel

Antag att vi vill analysera det asymptotiska beteendet för algoritmen Mergesort. Låt antalet element vi vill sortera vara <math>\,n</math> och låt tiden för att utföra sorteringen vara <math>\,T(n)</math>. Vi har då att

<math> T(n) = \begin{cases} \Theta(1) & \mbox{om } n = 1\\ T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil) + \Theta(n) & \mbox{om } n > 1\end{cases}</math>