 Rekursionsgleichung aufstellen |
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
 |
|
| Rekursionsgleichung aufstellen |
     |
Hallo,
für folgenden Algorithmus muss ich die Rekursionsgleichung aufstellen um die Laufzeit zu bestimmen.
der Algorithmus:
static void DreiSort(int[] A, int i, int j)
{
if (j - i <= 2)
{
if (A[i] > A[i + 1])
{
int temp = A[i + 1];
A[i + 1] = A[i];
A[i] = temp;
}
return;
}
DreiSort(A, i, j - (j - i) / 3); //ersten 2 drittel des Arrays
DreiSort(A, i + (j - i) / 3, j); //letzten 2 drittel des Arrays
DreiSort(A, i, j - (j - i) / 3); // die ersten 2 drittel des Arrays
}
Intuitiv denke ich, die Rekursionsgleichung ist:
T(n) = 3 * T(n/3), denn 3 Sort wird pro Auruf 3 mal aufgerufen und die Größe der Teilprobleme ist n/3, wobei n die Länge des Arrays ist.
Stimmt das so? Vielen Dank schon mal.
Grüße
|
|
29.04.2013 21:25 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
das sollte so passen.
VG,
Karlito
|
|
|
29.04.2013 22:51 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
ich denke ich habs jetzt. Die Größe der Teilprobleme ist ja (2/3)*n und nicht n/3, womit man T(n) = 3 * T((2/3)*n) + c erhält, für eine Konstante c, somit gilt T(n) = O(n^(log_2/3(3))) = O(n^2,71).
Grüße
|
|
|
30.04.2013 00:20 |
|
|
|
