[AD] Rekurrenzgleichung bilden
2007-11-21 20:42
Hannes
Hallo,
ich habe einen (Sortier-)Algorithmus, der ungefähr so aussieht:
Er ruft sich also in jedem Rekursionsschritt einmal selbst auf, mit einer Teilliste, die immer ein Element "kürzer wird" (r gibt das rechteste Element einer Teilliste an, auf der ALG arbeitet). Die Kosten für das Aufteilen sind konstant. Es ergeben sich also für eine Rekurrenzgleichung der Form
[latex]T(n) = a \cdot T\left( \frac{n}{b} \right) + f(n)[/latex]
die Werte a = 1 und f(n) = O(1). Aber was ist mit b? Im AD-Script steht, dass jedes Teilproblem die größe n/b hat. Irgendwie stehe ich gerade auf dem Schlauch und kann das nicht auf meinen Algorithmus übertragen.
Grüße
Hannes
ich habe einen (Sortier-)Algorithmus, der ungefähr so aussieht:
ALG(A, r):
if (r > 2):
ALG(A, r - 1)
// dinge tun auf der liste A[0...r]
Er ruft sich also in jedem Rekursionsschritt einmal selbst auf, mit einer Teilliste, die immer ein Element "kürzer wird" (r gibt das rechteste Element einer Teilliste an, auf der ALG arbeitet). Die Kosten für das Aufteilen sind konstant. Es ergeben sich also für eine Rekurrenzgleichung der Form
[latex]T(n) = a \cdot T\left( \frac{n}{b} \right) + f(n)[/latex]
die Werte a = 1 und f(n) = O(1). Aber was ist mit b? Im AD-Script steht, dass jedes Teilproblem die größe n/b hat. Irgendwie stehe ich gerade auf dem Schlauch und kann das nicht auf meinen Algorithmus übertragen.
Grüße
Hannes