Komplexizität - O Notation |
| 22.04.2008, 20:05 | Auf diesen Beitrag antworten » |
| xole_X | Komplexizität - O Notation Hallo ich muss von einem code die komplexizität bestimmen, was ich auch bereits getan hab...mein Problem liegt eher darin, wie man das zeug sauber aufschreibt. den code darf ich hier leider net posten, aber hier einfach nur ein anderes beispiel (konsumiert 2 gleichgroße nxn matrizen und addiert diese) 1. public sum(int a[][],int b[][]){ 2. int reihe = a.length; 3. int zeile = a[0].length; 4. int[][] summatrix = new int[reihe][zeile]; 5. 6. for(int i = 0; i<reihe; i++) 7. for(int j = 0; j<zeile; j++) 8. summatrix[i][j] = a[i][j]+b[i][j] 9. 10. return summatrix; 11. } ich hätte jetzt einfach bei meinem code gesagt: zeile2: c1 zeile3: c2 zeile4: c3 zeile6: n zeile7: n zeile8: c4 zeile10: c5 T(n) = c1+c2+c3+n*(n+c4)+c5 € O(n²) wie schreib ich das aber alles sauber auf? schreibt man da überhaupt für Konstante Aufrufe c hin oder schreib ich da ne 1 oder T(c1) oder T(1)... |
|
|
|
| 23.04.2008, 08:40 | Auf diesen Beitrag antworten » |
| ed209 | Wie genau es sein muß hängt vermutlich von Eurem Prof ab, aber ich würde die Konstanten c1, c2, c3 und c5 zu einer zusammenfassen, die Klammer ausmultiplizieren und dann über die Definition von O gehen. Gruß, ED |
| 23.04.2008, 12:02 | Auf diesen Beitrag antworten » |
| Tobias | Ich weiß nicht, ob ihr es so umständlich gelernt habt, aber im Allgemeinen gibt man konstanten Operationen den Kostenfaktor "1" bzw. lässt alle in der Eingabegröße konstanten Operationen sofort zu O(1) kollabieren. Man kann ja zeigen, dass es im O-Kalkül keinen Unterschied macht, denn wählte einfach dann erhälst du |
|
|
