Informatiker Board | Praktische Informatik | Komplexität von Algorithmen

Informatiker Board » Themengebiete » Praktische Informatik » Komplexität von Algorithmen - Bitte helft mir!

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexität von Algorithmen - Bitte helft mir!

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

martin26
Grünschnabel

Dabei seit: 03.02.2017
Beiträge: 1

Komplexität von Algorithmen - Bitte helft mir!

Zitatantwort auf diesen Beitrag erstellen

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 10:53

Nehmen Sie martin26 in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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]$

__________________
Syntax Highlighting fürs Board (Link)

03.02.2017 14:26

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Komplexität von Algorithmen - Bitte helft mir!