Aus Programmcode die Rekursionsgleichung bestimmen

pac89

hallo, ich habe folgenden
code :

sort (int [] A, int l, int r)
{
   if(A[l] > A[r])
   {
      exchange (A[l],A[r]);
   }

   if(l<r-1)
   {
      k:=(r-1+1) div 3;
         sort(A,l,r-k);
         sort(A,l+k,r);
         sort(A,l,r-k)
   }
}

und muss für den Aufruf sort(A,0,n-1) die rekursionsgleichung bestimmen.
nun weiß ich nicht so genau, wie ich vorgehen soll. ich kenn zwar die musterlösung T(n) = 3* T(2/3*n) + 1

aber nicht den weg...kann mir da jmd. weiterhelfen?

Für exchange und die restlichen nicht-rekursiven Schritte wird der konstante Aufwand 1 angenommen.
n ist unsere Problemgröße. Wir arbeiten mit einer linken Grenze l und einer rechten r. In solchen Fällen sagt man i.d.R. n = r-l.
Weiterhin gilt nach dem Code k = n/3

Wie groß ist das Interval also im ersten rekursiven Aufruf sort(A,l,r-k) noch?

Rechte Grenze minus linke Grenze:
(r-k) - l = r-l - k = n - n/3 = 2n/3

Analog die beiden anderen Fälle.

Jetzt nehmen wir pro Funktionsaufruf einen konstanten Aufwand 1 an (für exchange, die Vergleiche u.s.w.), haben 3 rekursive Aufrufe die das Interval auf 2n/3 stauchen und schon ergibt sich die Musterlösung.

Das war auf die schnelle. Falls die die Schritte klar sind, kannst Du es vllt noch etwas sauberer aufschreiben. Aber die Idee kommt hoffentlich rüber

pac89

okay...vielen dank. alles verstanden. aber eine frage habe ich noch: wieso lautet unsere Problemgröße n und nicht n-1, da ja der aufruf n-1 beinhaltet?

Ich habe nicht darauf geachtet, ob irgendwo eine -1 steht oder wie bei ganzzahliger Division gerundet wird. Sowas spielt meistens keine Rolle bei Bestimmung der Komplexität.

Nachtrag: Dein Array hat "trotzdem" n Elemente. Indiziert von 0 bis n-1. Aber wie gesagt: Sowas ist unerheblich.