[AD] Rekurrenzgleichung bilden

[AD] Rekurrenzgleichung bilden - Druckversion

+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Bachelorstudieng ( /forumdisplay.php?fid=112 )
+--- Forum: PM Praktische Informatik ( /forumdisplay.php?fid=98 )
+--- Thema: [AD] Rekurrenzgleichung bilden ( /showthread.php?tid=9141 )

[AD] Rekurrenzgleichung bilden - Hannes - 21.11.2007 20:42

Hallo,

ich habe einen (Sortier-)Algorithmus, der ungefähr so aussieht:

Code:

       
        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

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

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

RE: [AD] Rekurrenzgleichung bilden - doodles - 21.11.2007 20:53

also wenn deine Teilliste immer einen kürzer wird, dann musst du das Teilproblem mit T(n-1) aufrufen und nicht mit T(n/b). Das Master Theorem kannst du dann aber nicht benutzen, sondern musst eine der anderen Methoden verwenden.

RE: [AD] Rekurrenzgleichung bilden - Hannes - 21.11.2007 21:13

aah, klar. danke :)

RE: [AD] Rekurrenzgleichung bilden - theorinix - 21.11.2007 21:27

Eine Technik die meistens bei solch einfachen Beispielen geht wäre es,
wenn die Rekurrenzgleichung mit dem kleineren Argument (hier n-1) auf der rechten Seite wieder eingesetzt wird,
und das dann so oft gemacht wird (3-4 mal reicht meistens aus) bis man eine allgemeine Form für das kleinere Argument (hier n-i) erkennt. Der Anfang wäre hier:
T(n) = aT(n-1)+f(n)
= a[ aT(n-2)+f(n-1) ] +f(n)
= a[ a[ aT(n-3)+f(n-2) ] + f(n-1) ] +f(n)
= $a^3 T(n-3) + \sum\limits^2_{i=0}f(n-i)$
Daraus findet man sicher eine Form für r-faches "Abwickeln" und diese muss man mit vollständiger Induktion beweisen, was meist leicht ist, denn der Schritt von r auf r+1 ist ja genau das Einsetzen der Rekurrenz.
Diese Gleichung für T(n) mit dem maximal möglichen "Abwickeln" bis T(0)=c ergibt die Lösung, die allerdings noch hübscher wird, da a=1 und die Funktion f(n) bekannt ist: O(1) ist eine Konstante, z.B. d ...
Hilft das weiter?

RE: [AD] Rekurrenzgleichung bilden - Hannes - 21.11.2007 21:38

ja, danke. die substitutionsmethode ist klar, ich hing nur an der form der rekurrenzgleichung, da hab ich zu sehr um die ecke gedacht.