Rekursionsgleichung aufstellen |
| 29.04.2013, 21:25 | Auf diesen Beitrag antworten » |
| 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 |
|
|
|
| 29.04.2013, 22:51 | Auf diesen Beitrag antworten » |
| Karlito | Hallo, das sollte so passen. VG, Karlito |
| 29.04.2013, 23:13 | Auf diesen Beitrag antworten » |
| 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 |
| 30.04.2013, 00:20 | Auf diesen Beitrag antworten » |
| 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 |
| Anzeige | |
|
|
|
|
|
