Hallo!
Versuche gerade, die Laufzeit eines einfachen Algorithmus zu bestimmten, anhand des folgenden Beispiels:
https://www.tu-ilmenau.de/fileadmin/...uD-SS09-01.pdf (S.18, "Die Laufzeit von Straight Insertion Sort")
Zuerstmal glaube ich, dass der Algorithmus dort falsch ist. Wenn ich den so programmiere, wird mein Array nicht richtig sortiert: bei Array, dass von 10 bis 1 geht, wird die 10 nicht berücksichtigt. Die korrekte Implementierung sollte die folgende sein:
(so ist es auch hier umgesetzt:; http://www.brpreiss.com/books/opus4/html/page489.html)
Ich komme dann auch auf eine andere Laufzeit (S.19)
- im best case würde ich sagen, einfach n-mal: Die äußere Schleife wird für jedes Array-Element einmal durchlaufen aber die innere wird nie ausgeführt.
- im worst case: 5*(n-1)+ n*(i * 4)
> die äußere Schleife wird im worst case (n-1)-mal durchlaufen, es finden 5 Elementaroperationen statt: 1 Vergleich (i < n), 1 Inkrementierung (i++) und 3 Zuweisungen
> die innere Schleife wird im worst case i-mal durchlaufen (also erst 1mal, dann 2mal, dann 3mal,...), dort finden 4 Elementaroperationen stat (zwei Vergleiche,1 Zuweisung und 1 Dekrementierung), das ganze n mal (also (1 * 4) + (2 * 4) + (3 * 4) ...)
Ist das annähernd richtig?
Und falls der Algorithmus auf der Folie doch richtig sein sollte: Wieso wird denn die äußere Schleife n-mal durchlaufen, wenn die Schleife von 2 bis n geht?
Wäre super, wenn sich da jemand kurz Zeit nehmen könnte!
Versuche gerade, die Laufzeit eines einfachen Algorithmus zu bestimmten, anhand des folgenden Beispiels:
https://www.tu-ilmenau.de/fileadmin/...uD-SS09-01.pdf (S.18, "Die Laufzeit von Straight Insertion Sort")
Zuerstmal glaube ich, dass der Algorithmus dort falsch ist. Wenn ich den so programmiere, wird mein Array nicht richtig sortiert: bei Array, dass von 10 bis 1 geht, wird die 10 nicht berücksichtigt. Die korrekte Implementierung sollte die folgende sein:
Code:
final int[] p = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; // final int[] p = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int counterone = 0; int countertwo = 0; int x; int j; final int n = p.length; for (int i = 1; i < n; i++) { System.out.println("Außen Durchlauf Nr.:" + ++counterone); x = p[i]; j = i; while (j > 0 && x < p[j - 1]) { System.out.println(" Innen Durchlauf Nr.:" + ++countertwo); p[j] = p[j - 1]; j--; } p[j] = x; }
Ich komme dann auch auf eine andere Laufzeit (S.19)
- im best case würde ich sagen, einfach n-mal: Die äußere Schleife wird für jedes Array-Element einmal durchlaufen aber die innere wird nie ausgeführt.
- im worst case: 5*(n-1)+ n*(i * 4)
> die äußere Schleife wird im worst case (n-1)-mal durchlaufen, es finden 5 Elementaroperationen statt: 1 Vergleich (i < n), 1 Inkrementierung (i++) und 3 Zuweisungen
> die innere Schleife wird im worst case i-mal durchlaufen (also erst 1mal, dann 2mal, dann 3mal,...), dort finden 4 Elementaroperationen stat (zwei Vergleiche,1 Zuweisung und 1 Dekrementierung), das ganze n mal (also (1 * 4) + (2 * 4) + (3 * 4) ...)
Ist das annähernd richtig?
Und falls der Algorithmus auf der Folie doch richtig sein sollte: Wieso wird denn die äußere Schleife n-mal durchlaufen, wenn die Schleife von 2 bis n geht?
Wäre super, wenn sich da jemand kurz Zeit nehmen könnte!
Comment