| Die letzten 4 Beiträge |
| deppensido |
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 |
| deppensido |
hallo,
da muss noch irgendwo ein Haken sein. Denn ich habe gerade mittels Mastertheorem (1.Fall) und ausprobieren Laufzeit O(n) rausbekommen.
Aber O(n) kann ja nicht stimmen, da ein Sortieralgorithmus mindestens Zeit: O(n * log(n)) braucht. Wenn ich die Rekursionsfunktion leicht abänder:
T(n) = 3 * T(n/3) + n, würde mit Mastertheorem (2.Fall) Laufzeit:
O(n * log(n)) rauskommen. Aber ich kann mir dabei nicht erklären wo das
+ n herkommt. Im Anhang, habe ich mal das Mastertheorem eingefügt. Vielen Dank schon mal.
Grüße
deppensido hat dieses Bild (verkleinerte Version) angehängt:
|
| Karlito |
Hallo,
das sollte so passen.
VG,
Karlito |
| deppensido |
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 |
|
|
