Komplexität von Algorithmen - Bitte helft mir!

03.02.2017, 10:53

martin26

Komplexität von Algorithmen - Bitte helft mir!

1 public void stuff ( int n ) {
2 int h =4; // 1
3 int l = 2 ; // 1
4 int m = 3 ; // 1
5 for ( int i = 0 ; i < n ; i++) { //n+1
6 m += h ; //n
7 int j = 0 ; //n
8 while ( j<n ) { //(n+1)*(n)
9 if ( j<m) { //n*n/2
10 m −= j ; //n*n/2
11 } else {
12 m += j ; //n*n/2
13 }
14 j +=2; //n*n/2
15 for ( int o = 1 ; o < n ; o∗=2) {//n*n/2*(n+1)/2
16 l += o ∗ m % 5 ; //3*n*n/2*(n+1)/2
17 }
18 }
19 }
20 }

Ich habe Probleme beim Bestimmen der Komplexitätsklasse dieses Algorithmus. Im Moment komm ich bei einer Komplexitätsklasse O(n^3) raus. Danke schonmal! smile

03.02.2017, 14:26

Auf diesen Beitrag antworten »

eulerscheZahl

Zitat:

5 for ( int i = 0 ; i < n ; i++) { //n+1

eigentlich n, aber in der $[latex]\mathcal O[/latex]$ Notation egal.

Zitat:

while ( j<n ) { //(n+1)*(n)

$[latex]n \cdot \frac{n}{2}[/latex]$ , da j+=2.

Zitat:

15 for ( int o = 1 ; o < n ; o∗=2) {//n*n/2*(n+1)/2
16 l += o ∗ m % 5 ; //3*n*n/2*(n+1)/2
17 }

Das kann ich nicht lesen. Auf Unicode Tabellen habe ich gerade auch keine Lust.

Falls da etwas wie o += 2 in Zeile 15 steht, dann ist $[latex]\mathcal O(n^3)[/latex]$ korrekt.
Bei o *= 2 wäre es $[latex]\mathcal O(n^2 \log(n))[/latex]$

Neue Frage »

Antworten »

Komplexität von Algorithmen - Bitte helft mir!

Verwandte Themen