---

Geschrieben von xole_X am 22.04.2008 um 20:05:

  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)...

---

Geschrieben von ed209 am 23.04.2008 um 08:40:

 

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

---

Geschrieben von Tobias am 23.04.2008 um 12:02:

 

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