Kompl. v. Algor. berechnen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | a) Komplexität von Insertionsort
b) Komplexität von |
a) Der Algorithmus hat O(n²) - mir geht's jetzt darum, das nachzuvollziehen.
Dazu muss ich ja die Anzahl der Elementarereignisse zählen, richtig?
Da kenne ich:
- Wertzuweisung
- Vergleich
- arithmetische Operationen
- Rückgabe eines Wertes
Hier die Implementierung:
| 1: |
| | 2: | public class InsertionSort {
| | 3: |
| | 4: | public static void main(String[] args) {
| | 5: | int[] p = { 5, 3, 2, 6, 5, 2, 7, 0 };
| | 6: |
| | 7: | int[] g = sort(p);
| | 8: | for (int ff : g)
| | 9: | System.out.println(ff);
| | 10: | }
| | 11: |
| | 12: | private static int[] sort(int[] p) {
| | 13: | for (int i = 1; i < p.length; i++) {
| | 14: | int j = i;
| | 15: | int t = p[j];
| | 16: | while (j > 0 && p[j - 1] > t) {
| | 17: | p[j] = p[j - 1];
| | 18: | j--;
| | 19: | }
| | 20: | p[j] = t;
| | 21: | }
| | 22: | return p;
| | 23: | }
| | 24: | }
|
Da zähle ich in der Methode sort:
1 Wertzuweisung (int = 0)
i arithmetische Operationen (i-mal i++)
i Wertzuweisung (int j = i)
i Wertzuweisung (int t = p[j])
j Wertzuweisungen (p[j] = p[j - 1])
j arithmetische Operationen (j--)
i Wertzuweisungen p[j] = t
1 Rückgabe
D. h. ich habe 1 + 4*i + i*j*2 Wertzuweisungen
Und i*j arithmetische Operationen
Und 1 Rückgabe
Also (1 + 4i + ij2) + (ij) + 1 Elementarereignisse
= 2 + 4i + 3ij
Also ich komme da auf gar keinen grünen Zweig...
b) Angenommen ein Algorithmus hat die Formel: 5n-1
Gibt es eine Konstante [mm] c_0 [/mm] , sodass f(n) = 5n-1 < [mm] c_0 [/mm] * n, wobei n > [mm] n_0 [/mm] und [mm] n_0 [/mm] > 0
Lösung soll sein: c = 5, [mm] n_0 [/mm] = 1
Wie komme ich den auf die Werte? Ich meine klar, dass 5n größer ist als 5n-1, aber muss ich das nicht theoretisch ausrechnen, also die Ungleichung lösen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi!
Du musst eher betrachten, wie häufig die Befehle ausgeführt werden.
hier hast du eine schleife, die über alle Elemente des anfangsarrays läuft. Das heißt, sie lauft n mal.
Innerhalb der Schleife wird eine zweite schleife aufgerufen, die uber alle elemente des Ergebnisarrays lauft, und schaut, wo das aktuelle Element eingefügt werden muß. Im schlimmsten Fall lauft auch diese Schleife n mal. Das Innere dieser Schleife benötigt nun eine Zeit t, und wird von der inneren Schleife n mal durchlaufen. Und das ganze wird von der
äußeren schleife ebenfalls n mal aufgerufen, daher dauert das ganze schlimmstenfalls t*n*n, also mit der Ordnung n ^2 .
jetzt läuft die innere schleife nicht immer n mal, weil das Ergebnisarray ja wächst und die schleife anfangs scheller fertig ist. Aber das sorgt nut dafür, dass sich die insgesamt benötigte Zeit um einen konstanten Faktor verringert. Es ändert nix am [mm] n^2 [/mm] .
die meisten Befehle sind von der ordnung 1, du musst nur schleifen genauer betrachten. Und wenn du vorgefertigte befehle aus bibliotheken o.ä. verwendest, können die auch ne höhere Ordnung haben.
|
|
|
| |
|
Okay, super! Danke für die Erklärung!
|
|
|
|
