Laufzeitberechnung

Hallo,

ich habe im Internet ein Programmstück gefunden, bei dem ich die O-Notation nicht verstehe (allgemein verstehe ich sie nicht vollständig).

Java:
for (i = 0; i < k; i++) { 
   for (j = 0; j < k; j++) {  
     brett[i][j] = 0;
   }
}
Die erste Schleife wird k-mal durchlaufen, die innere ebenfalls. Daher ergibt sich die Anzahl der durchläufe mit k². Warum ist die O-Notation aber O(n)?
 

XHelp

Top Contributor
Weil die Quelle falsch ist, weil n=k² ist, weil es sich auf ein anderes Stück bezieht, weil k keine Rolle spielt, weil weil weil.

Gib mal an wo du es her hast, so aus dem Zusammenhang gerissen kann man rein gar nichts sagen.
 

XHelp

Top Contributor
Da geht man davon aus, dass es immer ein quadratisches Array ist, so dass n=k² ist. Man gibt quasi als Parameter nicht n=3 für 3x3 Matrix, sondern n=9 für 3x3 Matrix.
 
Und bei dem Programmstück gleich daneben? Geht man dann davon aus, dass das Array die Größe n hat, und somit n^2 Durchläufe erforderlich sind?

Hier wäre die O-Notation doch: Laufzeit(n)=O(n²):

Java:
static int sum(int[][] a) { 	 
int n = a.length; 	 
int sum = 0; 	 
for (int i = 0; i < n; ++i) { 	 
for (int j = 0; j < n; ++j) {	 
sum += a[i][j]; 
}
}	 
 	 
 return sum; 	 
}
 
Zuletzt bearbeitet:

Ähnliche Java Themen

Neue Themen


Oben