# Schleifen & O Notation



## Xpisto (28. Jan 2012)

Hey Leute, ich hab einfach ein enormes Problem aus gegebenen Programmcodes die O Notation zu bestimmen, hat einer einen Tipp woran ich erkenne welche Zeitkomplexität der gegebene Programmteil besitzt? ich wäre euch überaus dankbar.

Z.b


```
O-Notation in 
Abhängigkeit von der Eingabegröße n. Hinweis: Der Aufwand für die Initialisierung von 
arr kann dabei vernachlässigt werden. 
   
static int[][][] func(int n) 
{ 
     int[][][] arr = new int[n][n][n]; 
        for(int i=1; i<3; i++) 
         { 
             for(int j=0; j<arr.length; j++) 
             { 
                  for(int k=0; k<arr.length; k++) 
                  { 
                   arr[i][j][k] = n; 
                     } 
             } 
         } 
return arr; 
}
```

Laut Lösung wäre das O(n²) Irgendwo auch nachvollziehbar, aber mir fehlt halt das verständnis von alleine drauf zu kommen, wie komme ich denn auf sowas? 

Würd mich echt freuen wenn mir jemand einen tipp gibt, ich hab echt keine ahnung wie ich eine allegemeine faustregel aufstellen kann. Ich mach das eher nach gefühl, aber da muss es doch was geben was bombensicher ist.


----------



## gasssst (28. Jan 2012)

Xpisto hat gesagt.:


> aber da muss es doch was geben was bombensicher ist.



Zählen ?


----------



## Xpisto (28. Jan 2012)

Was denn zählen?


----------



## njans (28. Jan 2012)

```
for(int i=1; i<3; i++)  // 3 mal das Ganze
         { 
             for(int j=0; j<arr.length; j++) // n mal das Ganze
             { 
                  for(int k=0; k<arr.length; k++)  // n mal das Ganze
```

Daraus ergibt sich O(3*n*n) = O(3n²) = O(n²)


----------



## gasssst (28. Jan 2012)

Xpisto hat gesagt.:


> Was denn zählen?



Deine Iterationen, oder hast du nicht verstanden was die O-Notation darstellt?


----------



## sung (28. Jan 2012)

arr_[j][k] = n   lauft  3*n*n  Male._


----------



## Xpisto (28. Jan 2012)

Ok dass lässt sich schon gut nachvollziehen, hier hätte ich z.b. ein O(log (n)) wie kommt das zu stande?

for(i=1; i<n; i*=2) 
    System.out.println(i);



Oder sowas hier

for(i=1; i<n; i++) 
    System.out.println(i); 
for(i=n; i>0; i--); 
    System.out.println(i); 

Das ergebnis ist O(n) aber ich würde sagen O(n²)..... Begründung: Erste schleife läuft n male und zweite ist auch abhängig von n, das n gibt die startgröße an und somit auch die anzahl der durchläufe.


Ich bin echt zu blöd  Und dabei ist es auch so wichtig für die kommende klausur.


----------



## XHelp (28. Jan 2012)

gibt an, wie oft du n durch 2 teilen kannst. Da 
	

	
	
		
		

		
		
	


	




 und log(2) eine konstante ist, kannst du bei O-Notationen auf die Basis nicht achten

P.S. log(n) gibt auch an wie viele Stellen die Binärdarstellung von n brauchen würde.


----------



## Xpisto (28. Jan 2012)

Ok macht auch Sinn. Es macht wirklich alles Sinn was ihr schreibt nur komm ich imer auf andere lösungen....


----------



## gassst (28. Jan 2012)

Xpisto hat gesagt.:


> for(i=1; i<n; i++)
> System.out.println(i);
> for(i=n; i>0; i--);
> System.out.println(i);
> ...



Und wo kommst du da auf n^2 ? Warum gehst du nicht einfach vor und zählst die Iterationen (oder führst den Code aus und zählst die prinln()s), wie ich gesagt hab: 
für n = 10 wird die erste Schleife 10 mal durchlaufen, die zweite Schleife 10 mal, also insgesamt 20 mal (O(n)), nicht 100 mal (O(n^2))


----------



## Xpisto (28. Jan 2012)

Was meinst du genau mit iterationen? Sry ich bin nicht so gut in Java. Das mit dem zählen ist keine schlechte idee, nur eins versteh ich nicht so recht vllt brauch ich ncoh ein zwei denkanstöße bevor es klick macht, wenn du sagst n= 10 udn es kommt 20, ach schwer zu beschreiben was ich meine.... Das 10*10 = 100 und n² nicht mehr klappt hab ich jetzt auch verstanden, hast du ein anderes beispiel was mir vllt die augen öffnet?

Vllt 2^n oder n³.

Ich versuchs wirklich nachzuvollziehen und streng mich an ^^

Danke schonmal für die netten Tipps von euch allen!


----------



## HoaX (28. Jan 2012)

Wenn die Schleifen geschachtelt sind, dann wird multipliziert. Sind die Schleifen sequenziell(nacheinander) dann addiert:

Pseudocode:

```
//Zwei mal geschachtelt, O(n) * O(n) = O(n²)
for(0..n) {
    for(0..n) {
        machWas();
    }
}
```


```
//Zwei mal geschachtelt, O(n) * O(n/2) = O(n²/2) = O(n²)
for(0..n) {
    for(0..(n/2)) {
        machWas();
    }
}
```


```
//Genauso wie zuvor O(n²)
for(0..n) {
    for(0..(n/2)) {
        machWas();
    }
}

// Hier nochmal O(n)
for(0..n) {
    machNochWasAnderes();
}

// Zusammen dann O(n²) + O(n) = O(n² + n) = O(n²)
```

Ansonsten bring du doch noch ein Beispiel und schreib dazu bei welcher Zeile du welchen Schluss ziehst, also + oder * und auf was du kommst.


----------



## Xpisto (28. Jan 2012)

Danke schonmal für deine Hilfe, ich hab hier ein paar Beispiele und meien Lösungen, bitte nicht zu streng sein 


```
public static void eins(int n) 
  { 
    int i = 1; 
    while (i < n) 
    { 
      System.out.println(i); 
      i = i * 2; 
    } 
  } 

/*
Schau mal:

n=10;  dann kommen folgende println raus 2,4,8,16

O(n/2 - 1) = O(n)  richtig begründet oder zufalltreffer oder gar nicht richtig?
*/
   
  public static void zwei(int n) 
  { 
    int i = 1; 
    while (i < n) 
    { 
      for (int j = 1; j <= 10; j++) 
        System.out.println(j); 
      i = i + 2; 
    } 
  } 

/* O(n) mit der begründung die whileschleife wird O(n-1) = O(n) und die for lassen wir aussen vor, da keine beziehung zu n vorhanden ist (Vorfaktor?)*/
   
  public static void drei (int n) 
  { 
    int i = 1; 
    while (i < n) 
    { 
      for (int j = 1; j <= i; j++) 
        System.out.println(j); 
      i = i + 2; 
    } 
  } 

/* fällt mir nichts zu ein.....*/

void proz1(int n) 
{ 
    int k=0; 
    int p=0;  
 
    while (p != n) 
    {   
       if(p < 7) 
       {    
          k++; 
       } 
 
       while (k > 7) 
       {   
          k--; 
       } 
       p++; 
   } 
} 
 
/*Aufrufe sind bei n=5 --> 1.Durchlauf k=1,p=1| 2.Durch k=2,p=2 | 3.D k=3,p=3 | 4.D k=4,p=4 | 5.D k=5, p=5   somit bei n=5 ; 5 Aufrufe also O(n)*/
 
 void proz2(int n) 
{ 
    int k=1; 
    int p=1;  
 
    while (p < n) 
    { 
       while(k < n) 
       {    
          k = 2 * k; 
       } 
       p++; 
    } 
} 

/*hier hab ich bei n=5 folgende aufrufe --> 4 mal wird die erste whileschleife aufgerufen und 3 mal die zweite whileschleife, beide sind von n abhängig also insgesamt wurden 7 aufrufe getätigt..... 
Ich versuch irgendwie versuchen das zu rechnen z.b für n 5 bei n² = 25 wir haben 7 aufrufe also nein dann kann ich alle n hoch 3-4 ausschliessen wenn ² schon nicht geht... ich find keinen vernünftigen Ansatz dazu...*/

public long func(int n) 
{ 
    long l = 0; 
    for(int i=0; i<10000; i++) 
    { 
        for(int j=0; j<n; j++) 
        { 
            for(int k=1; k<n; k++) 
            { 
                l++; 
            } 
        } 
    } 
    return l; 
} 

/*hier würde ich einfach O(n²) sagen weil die erste schleife nicht abhängig von n ist, also ist das ein vorfaktor, die zweiteschleife wird n mal durchlaufen n-1 mal durchlaufen also O(n*n-1) = O(n²) hab ich das richtig erklärt?*/
```


Danke dass du mir hilfts


----------



## HoaX (28. Jan 2012)

> ```
> public static void eins(int n)
> {
> int i = 1;
> ...


Nö, erstens: Wieso 2,4,8,16? wenn n=10 ist, wie soll dann 16 ausgegeben werden? Es wird 1,2,4,8 ausgegeben!
Noch wäre deine Formel korrekt, aber nimm doch mal n=20, dann kommt nämlich 1,2,4,8,16 ... also falsche Formel.
Du verdoppelst ja immer die Zahl, also muss man überlegen wie oft man n durch 2 teilen kann -> O(log2(n))



Weiter gehts...


> ```
> public static void zwei(int n)
> {
> int i = 1;
> ...


Jein, O(n) stimmt, aber: die while-Schleife läuft n/2, da du ja immer +2 machst, die for-Schleife läuft immer 10 mal, also O(n/2) * O(10) = O(n)


----------



## Xpisto (28. Jan 2012)

Ich sitz hier mit dem kollegen und wir sind wirklich am verzweifeln, ich versteh es nicht ..... Ich möcht dich auch ungern damit nerven, aber du bist derzeit unsere einzige hoffnung ^^

Vorab, wie siehts denn mit den andewren as, total daneben oider was brauchbares dabei?

Wieso ist dir so klar dass du n/2 teilen muss, woraus ewird das ersichtlich? Also du sagst j das so selbstverständlich und ich kanns nicht nachvollziehen, das demotivert mich echt  Bin ich zu blöd oder hab ich irgendwo eine lücke? Das mit der ausgabe hast recht, hab mich vertan aber eher wegen flüchtigkeit als wegen mangelden verständnis.


----------



## HoaX (28. Jan 2012)

Xpisto hat gesagt.:


> Wieso ist dir so klar dass du n/2 teilen muss, woraus ewird das ersichtlich? Also du sagst j das so selbstverständlich und ich kanns nicht nachvollziehen, das demotivert mich echt  Bin ich zu blöd oder hab ich irgendwo eine lücke? Das mit der ausgabe hast recht, hab mich vertan aber eher wegen flüchtigkeit als wegen mangelden verständnis.


Das sind halt Mathegrundlagen: Deine Methode multipliziert immer *2 bis das Ergebnis x > n ist. Als Potenz ausgedrückt 2 hoch x > n. Und x ist deine gesuchte Anzahl durchläuft, dein O. Umgedreht kannst du dich auch fragen wie oft muss ich n durch 2 teilen, bis es 1 ist. Die Anzahl der Schritte bleibt gleich. Und um 2 hoch x = n nach x aufzulösen schreibt man x = log2(n).


----------



## XHelp (28. Jan 2012)

Xpisto hat gesagt.:


> Wieso ist dir so klar dass du n/2 teilen muss


Weil du immer +2 rechnest, und das kannst du eben nur "n/2" mal machen, bist du n erreichst.


----------



## HimBromBeere (29. Jan 2012)

Bei der O-Notation interessiert dich grundsätzlich nur die höchste Potenz von n (=Anzahl sich widerholender gleicher Schritte). D.h. wenn du sowas hast wie O(n^2 + n -3) ist das einfach die Ordnung O(n^2), weil alle anderen Potenzen halt kaum noch ins Gewicht fallen. Auch etwaige Vorfaktoren sind weitgehend irrelevant (in deinem Fall 3*n^2), wichtig ist meist nur, wie sich die Laufzeit mit steigender Anzahl Schritte funktionell entwickelt.


----------



## Razuer (29. Jan 2012)

HoaX hat gesagt.:


> Das sind halt Mathegrundlagen: Deine Methode multipliziert immer *2 bis das Ergebnis x > n ist. Als Potenz ausgedrückt 2 hoch x > n. Und x ist deine gesuchte Anzahl durchläuft, dein O. Umgedreht kannst du dich auch fragen wie oft muss ich n durch 2 teilen, bis es 1 ist. Die Anzahl der Schritte bleibt gleich. Und um 2 hoch x = n nach x aufzulösen schreibt man x = log2(n).




Hallo Hoax, auch ich verzweifle irgendwie an deiner Erklärung. Also nicht dass sie falsch wäre nein, nein. Trotzdessen du es eigentlich schon recht ausführlich erklärst hast ergibt sich für mich kein genauer Zusammenhang... 

Ziel des ganzen ist ja iwie auf die ONotation zu kommen und trotz genauster Erklärung komm ich nicht drauf klar, inwiefern man auf den LOG kommen kann / bzw. kommen muss wenn man konstant +2 rechnet - warum soll ich mich dann fragen wie oft man durch teilen muss ? und warum kommt da der log raus? könnte sich vll einer der es wirklich gut kann irgendwie für mathedummies erklären  ? bitte wäre wirklich sehr hilfreich!


----------



## Razuer (29. Jan 2012)

Wenn ich jetzt den vorangegangen Quelltext nehme:


```
public static void zwei(int n) 
  { 
    int i = 1; 
    while (i < n) 
    { 
      for (int j = 1; j <= 10; j++) 
        System.out.println(j); 
      i = i + 2; 
    } 
  }
```

Und ich für n bspw. jetzt den Wert 10 nehme erfolgt der Ablauf wiefolgt: 

i=1 >> 

while (1<10) [Bedingung erfüllt betritt die while Schleife)

for(int j=1; j<=10; j++)

3= 1+2  (für j=1) 
5=3+2 (für j=2)
7=5+2 (für j=3)
9=7+2 (für j=4)
11=9+2 (für j=5)
13=11+2 (für j=6)
..
...
...
21 = 19+2 (für j=10) 

die for Schleife wird somit 10 mal ausgeführt. mit der while passiert ja eigentlich nichts mehr. Sie wird das erste mal betreten und gut ist. 

Nur wieso kommt man jetzt auf die Idee dass es dann direkt n/2 sein muss? Laut der Begründung von Hoax ist es sofort klar, dass man n/2 rechnen muss! ? das * 10 würde sich für mich noch insofern erklären, da die for Schleife halt 10 mal aufgerufen wird aber warum n/2? 

Gibts da irgendwie sone Gegenrechnung wie man auf die n/2 kommen kann? also kann man es irgendwie zurückrechnen, damit es sich irgendwie nachvollziehen lässt? 

Auch wenn es euch vielleicht auf die Nerven geht aber es wäre wirklich mehr als nett wenn mir jemand helfen könnte diesen (anscheinend) doch recht simplen Zusammenhang zu erklären :S


----------



## HoaX (29. Jan 2012)

Razuer hat gesagt.:


> ...
> Ziel des ganzen ist ja iwie auf die ONotation zu kommen und trotz genauster Erklärung komm ich nicht drauf klar, inwiefern man auf den LOG kommen kann / bzw. kommen muss wenn man konstant +2 rechnet - warum soll ich mich dann fragen wie oft man durch teilen muss ? und warum kommt da der log raus? könnte sich vll einer der es wirklich gut kann irgendwie für mathedummies erklären  ? bitte wäre wirklich sehr hilfreich!


Wenn du meine Erklärung nochmal liest, dann siehst du dass da *2 steht, nicht +2!


----------



## Paddelpirat (29. Jan 2012)

@Razuer Ich hab den Eindruck du verstehst den Code nicht ganz richtig. Deswegen setz ich mal zusätzliche geschweifte Klammern rein:


```
public static void zwei(int n) 
  { 
    int i = 1; 
    while (i < n) 
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
      i = i + 2; 
    } 
  }
```

Angenommen n=10. Du kommst in die while-Schleife rein mit i=1 (< 10 erfüllt). 
Dann gehst du in die for-Schleife mit j=1 (<=10).
jetzt wird j ausgegeben:
1
2
...
10

Diese 10 Ausgaben sind allerdings nicht von n abhängig, also sind sie in der O-Notation nur als eine Konstante verborgen.
Jetzt ist die for-Schleife fertig und du erhöhst i um 2. Also ist i nun 1+2=3
Dann kommst du wieder oben in der while-Schleife an und überprüfst: 3 < 10 (erfüllt), gehst also in die for-Schleife und so weiter.

So nun ist die while-Schleife aber von n abhängig und du erhöhst i in jedem Durchlauf um 2, also kommst du doppelt so schnell bei n an, als wenn du i in jedem Schritt um 1 erhöhen würdest. Somit hast du dann deine n/2.


----------



## Razuer (29. Jan 2012)

Danke für eure Antworten! 

Den Code als solches habe ich wirklich gerade erst vor paar minuten gepeilt ^^ 

die for schleife an sich wird 10 mal ausgeführt 

aber beim fünften durchlauf ist i nicht mehr kleiner n da nämlich 11 nicht < 10 ist soweit leuchtet ein. 

also wenn ich n/2 rechne erhalte ich 5 der zusammenhang ist schon einmal hergestellt. problem ist trotzdem die "erkenntnis" also für "euch" ist es ja schon einmal "direkt" klar dass es n/2 sein muss! wenn man etwas +2 macht dass man automatisch durch 2 teilen muss 

ich würde jetzt maximal auf n/2 kommen indem ich halt meine werte einsetze und schaue was ich mit den werten von 10 und 5 anfange ... ja 10/5 = 2 hurra ... 

man ich weiß einfach nicht wie ich es verständlich beschreiben soll dabei erklärt ihr es ja schon richtig für dumme ^^

ich denke dass mir diese aussage 





> also kommst du doppelt so schnell bei n an, als wenn du i in jedem Schritt um 1 erhöhen würdest. Somit hast du dann deine n/2.


 dann noch am ehesten hilft


----------



## Paddelpirat (29. Jan 2012)

Okay zum besseren Verständnis eine kleine Aufgabe für dich: Schreib mir mal den Code so um, dass du statt der while-Schleife eine weitere for-Schleife hast. Also:


```
public static void zwei(int n) 
  { 
    //int i = 1; <----Das brauchst du in dem Fall an dieser Stelle nicht mehr, sondern in der for-Schleife
    for(?;?;?) { //<----Hier geeignete werte einsetzen
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```


----------



## Xpisto (29. Jan 2012)

Ich sitze gerade mit Razuer an einem Tisch und deshalb poste ich mal die lösung der "aufgabe"^^


```
public static void zwei(int n) 
  { 
    //int i = 1; <----Das brauchst du in dem Fall an dieser Stelle nicht mehr, sondern in der for-Schleife
    for(int=1;i<n;i++) { //<----Hier geeignete werte einsetzen
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```


----------



## Paddelpirat (29. Jan 2012)

Fast richtig. Wieso schreibst/t du/ihr nur i++? Ihr erhöht den wert in der while Schleife doch um 2 in jedem Schritt.

Edit: und in dem ersten Term muss 
	
	
	
	





```
int i=1
```
 stehen  (das i fehlt)


----------



## Xpisto (29. Jan 2012)

ja du hast recht, das hab ich nicht berücksichtigt.


----------



## Paddelpirat (29. Jan 2012)

Okay, wenn du das korrigiert hast, kannst du die for-Schleife mal so schreiben, dass du in jedem Schritt i nur um 1 erhöhst. Wie muss dann der mittlere Term der for-Schleife aussehen?


----------



## Xpisto (29. Jan 2012)

1.Aufgabe 2er Schritte

```
public static void zwei(int n) 
  { 
 
    for(int i=1;i<n;i+2) { 
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```

2.Aufgabe 1er Schritte

```
public static void zwei(int n) 
  { 

    for(int i=0;i<n;i++) { 
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```


So wenn ich deine Aufgabe richtig verstanden habe ^^


----------



## AmunRa (29. Jan 2012)

Nein zweiter Teil ist nicht richtig ,
da ja jetzt die schleife 10 x ausgeführt wird. und nicht wie zuvor nur 5 mal (spreche von der äusseren Schleife)


----------



## Xpisto (29. Jan 2012)

Paddelpirat hat gesagt.:


> Okay, wenn du das korrigiert hast, kannst du die for-Schleife mal so schreiben, dass du in jedem Schritt i nur um 1 erhöhst. Wie muss dann der mittlere Term der for-Schleife aussehen?



Das war die Aufgabe, oder hab i9ch was falsch verstanden?


----------



## AmunRa (29. Jan 2012)

ja nur du hast den mittleren Term nicht richtig angepasst



(P.S unwichtig: du hast den ersten Term der schleife auch verändert dort sollte noch immer int i = 1 stehen und nicht int i=0)


----------



## Paddelpirat (29. Jan 2012)

Genau genommen sind beide Aufgabenteile noch nicht ganz korrekt. Ich geb mal die Lösung für den ersten Teil an, da es nur eine Kleinigkeit ist:


```
public static void zwei(int n) 
  { 
 
    for(int i=1;i<n;i+=2) { //i+=2 bedeutet i=i+2 
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```

Zum zweiten Teil habe ich gesagt, dass insb. der mittlere Term der for-Schleife verändert werden muss, also nochmal  Denn so wie du es geschrieben hast, liefert die Methode ein anderes Ergebnis als in Aufgabe 1.


```
public static void zwei(int n) 
  { 

    for(int i=1;?;i++) { //Hier das Richtige für ? einsetzen.
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```

Edit: Vielleicht solltet ihr auch einfach mal ein kleines TestProgramm schreiben, was die Methode 
	
	
	
	





```
zwei
```
 aufruft....


----------



## Xpisto (29. Jan 2012)

Achso du möchtest dass die gleiche Ausgabe erzeugt wird, dann würd ich auf anhioeb sagen


```
public static void zwei(int n) 
  { 
 
    for(int i=1;i<=n/2;i++) { //für n=10 wird die for 5 mal aufgerufen
    { 
      for (int j = 1; j <= 10; j++) {
        System.out.println(j);
      } 
    } 
  }
```


----------



## XHelp (29. Jan 2012)

Wenn du die Zahl 10 hast und immer +2 rechnest, bis du die Zahl erreichst, dann machst du ja: 10<=2+2+2+2+2, was genau das selbe ist wie 10<=5*2. Die 2 hast du, 10 ist dein n, also musst du es nach 5 umstellen: 10/2<=5; also ist deine Gesuchte Laufzeit: n/2.

Aber ein Tipp, der ernst gemeint ist, aber bis jetzt nicht gefallen ist: nimm es einfach hin! Wenn die entweder die Grundlagen in Programmieren oder Mathematik fehlen, dann musst du die entweder selber nachholen... oder eben die Beispiele auf den 2 Seiten einfach nur auswendig lernen.
Ich nehme mal an das brauchst du für irgendein Fach/Prüfung - da gibt es nur eine kleine Anzahl an "Möglichkeiten", die abgefragt werden.


----------



## Xpisto (29. Jan 2012)

Ja das Problem mit dem Auswendig lernen ist ja kein problem, zumal wir in unserere prüfung an der uni ein dina 4 blatt als hilfe mitnehmen dürfen. Allerdings erkenne ich aus den verschiedenen Ausfgaben selten parallelen.

Also was wäre jetzt ein programm faustregel log n ?


----------



## XHelp (29. Jan 2012)

Wenn du von n bis 1 immer 
	
	
	
	





```
/x
```
 machst, oder von 1 bin immer 
	
	
	
	





```
*x
```
. Aber "Faustregel" gibt es da nicht.


----------



## Xpisto (30. Jan 2012)

Kann mir einer erklären wie man bei so einer Aufgabe vorgeht? Die O Notation anhand des Codes ablesen kreg ich schon einigermaßen gut hin, aber das versteh ich von vorne bis hinten nicht Oo





Uploaded with http://imageshack.us


----------



## HimBromBeere (30. Jan 2012)

DAS soll O(n3) sein?! Nie im Leben! Wie du siehst, wird die Anzahl der Durchläufe jedes Mal vervierfacht, dabei kommen etwa 20ms Zeit drauf... es ist also ein linearer Anstieg der Laufzeit bei exponentiellem Anstieg der Durchläufe... gib mal einen Tipp ab, worauf das hindeuten könnte...


----------



## Xpisto (30. Jan 2012)

absolut keine ahnung wie kann ich denn da vorgehen? bei dem Programm weiss ich nun dass ich zählen muss aber hier?


----------



## HimBromBeere (30. Jan 2012)

Versuche mal, eine Vorschrift zu bauen, wie du aus der Anzahl der Durchläufe auf eine Zeit kommst (also irgendwas der Form t = t(n))


----------



## Xpisto (30. Jan 2012)

ich weiss wirklich nicht wie ichs machen soll, wär super wenn du mir das erklärst, weil es könnte morgen in der prüfung eine kleine aufgabe dazu geben aber nur vielleicht!


----------



## HoaX (30. Jan 2012)

Na dann: Mut zur Lücke!


----------



## XHelp (31. Jan 2012)

Es gibt nicht so viele Standard-O-Klassen. Rechne doch alle durch, dann wirst du sehen, dass eine Klasse perfekt reinpasst.


----------



## xKoRe (31. Jan 2012)

Bei der O Notation gibt es zwei Unterschiede. Der exakte Aufwand und die Aufwandsklasse. Wobei bei beiden mit der Abhängigkeit von (meist) einer Variable geredet wird.

Standardmässig nennen wir sie mal n.

Hast du also eine Schleife die über n Elemente geht, sprechen wir vom Aufwand x*n (Wobei x die Anzahl der Berechnungen/Aufwände pro durchlauf ist. Was man da alles mitrechnet, hängt in der Regel vom Prüfer oder dem Ziel der Aufwandsberechnung ab.). Die Aufwandsklasse wäre, sofern bei x * n --> x selbst nicht mehr weiter abhängig von n ist: n. D.h. auch 3*n liegt noch in O(n). Hast du ein Konstrukt wie n^3 + n^2 + n gewinnt das Höchste bei der Aufwandsklasse: O(n^3). 

Aufwandsklassen (nach Reihenfolge weitesgehend)

log(n)
n
n * log(n)
n^2
n^2
.
.
.
2^n
3^n

etc. 

Es gibt Pauschal keine Formel von der ich wüsste mit der du aus einer Berechnung die Aufwandsklasse bestimmst. Das klappt lediglich durch nachdenken und Begründen. 

Ein paar Tipps:
logx(n) ist im Prinzip das gegenstück zu x^n --> wächst der Aufwand also exponentiell um den Faktor n, haben wir x^n. Sinkt er um einen n Faktor, logx(n). 

d.h. eine Schleife, in der sich beispielsweise die Zählvariable immer verdoppelt bis sie am "Ende" angelangt ist, hätten wir einen logarithmischen Aufwand. (sogar zweierlogarithmus)

Ansonsten gilt noch: Haben wir eine Schleife in einer Schleife, multiplizieren wir deren Aufwand miteinander und erhalten somit den neuen Aufwand.

äussere Schleife n, innere Schleife n^2
--> Zusammen n^3

viel Erfolg


----------



## gaaaaast12341 (1. Feb 2012)

Hi, eine frage, folgender Code ist gegeben



```
For (int i= 0; i<10*n*n; i+=2)   // 10*n/2*n/2
{

           For(int j=1; j <= 223; j++)    //223
            { 
                   For(int z=1; Z< n*n;z++)   // n^2
                    {  tuwas();
                     }
              }
   }
```
Muesste doch O(n^4) sein oder?


----------



## HimBromBeere (1. Feb 2012)

Ja, auch wenn 





> // 10*n/2*n/2


ziemlich mir ziemlich suspekt aussieht... da ist irgendwie eine 2 zu viel


----------



## XHelp (1. Feb 2012)

xKoRe, entweder hast du dich falsch ausgedrückt oder ich muss dir widersprechen:
Bei der O-Notation gibt es keinen "exakten Aufwand". Es gibt natürlich eine exakte Laufzeit, aber das hat nichts mehr mit O-Notation zu tun. Darüber hinaus ist O(3n) *genau die selbe* Menge wie auch O(n), O(n+100), O(n+log(n)) usw.


----------



## HimBromBeere (1. Feb 2012)

Hat er doch gesagt


> D.h. auch 3*n liegt noch in O(n)


----------



## XHelp (1. Feb 2012)

Das alles bezieht sich auf die Aussage mit dem exaktem Aufwand. Da gibt es bei O-Notation kein "entweder ist es das oder das". Das ist alles das selbe.


----------



## Xpisto (1. Feb 2012)

hey ich hab gestern über den gast account geschrieben weil ich über dem handy geschrieben habe. Irgendwie ist keiner auf mein ergebnis eingegangen soondern nur auf die antwort meines vorgängers  Kann mir jemand sagen ob ich O(n^4) richtig ist?


Noch eine andere Frage:

Wurzel(n-1) * log(n) * Wurzel(n)

Ist O(log(n)) richtig oder wäre O(Wurzel(n)) richtig?

Nächste Frage

n(n-1) + n² = O(n³)  

Diese Aussage ist doch falsch oder? O(n³) wächst schneller als die linke gleichung.


----------



## XHelp (1. Feb 2012)

1. Darauf wurde doch eingegangen, ließ den Post von HimBromBeere
2. plot sqrt(n), log(n) n=1 to 100000 - Wolfram|Alpha
3. Dadurch dass n³ schneller wächst, ist ja die Aussage richtig. Aber wie kommst du denn von n+n² auf n³???


----------



## langhaar! (1. Feb 2012)

Xpisto hat gesagt.:


> Nächste Frage
> 
> n(n-1) + n² = O(n³)
> 
> Diese Aussage ist doch falsch oder? O(n³) wächst schneller als die linke gleichung.



Die Aussage ist richtig.
Das = ist eine (schlampige) Vereinfachung und müsste eigentlich 'ist Element von' heissen.


----------



## XHelp (1. Feb 2012)

Gleichheitszeichen ist bei der O-Notation zulässig. Es ist zwar rein formal gesehen nicht richtig (ist ja keine Gleichung, außerdem ist das eine eine Funktion und das andere eine Menge), aber bei der O-Notation eben "erlaubt".


----------



## langhaar! (1. Feb 2012)

XHelp hat gesagt.:


> Gleichheitszeichen ist bei der O-Notation zulässig. Es ist zwar rein formal gesehen nicht richtig (ist ja keine Gleichung, außerdem ist das eine eine Funktion und das andere eine Menge), aber bei der O-Notation eben "erlaubt".



Ich habe nichts anderes geschrieben, oder?
Ich vermute aber, dass der TE Schwierigkeiten hatte, weil das verwendete = keine symmetrische Relation impliziert.


----------



## XHelp (1. Feb 2012)

Ich habe dann deinen Hinweis mit "müsste eigentlich" falsch interpretiert. Nehme alles zurück


----------



## HimBromBeere (1. Feb 2012)

> Wurzel(n-1) * log(n) * Wurzel(n)
> 
> Ist O(log(n)) richtig oder wäre O(Wurzel(n)) richtig?


Sollte es nicht O(n*log(n)) sein?


----------



## xKoRe (1. Feb 2012)

XHelp hat gesagt.:


> xKoRe, entweder hast du dich falsch ausgedrückt oder ich muss dir widersprechen:
> Bei der O-Notation gibt es keinen "exakten Aufwand". Es gibt natürlich eine exakte Laufzeit, aber das hat nichts mehr mit O-Notation zu tun. Darüber hinaus ist O(3n) *genau die selbe* Menge wie auch O(n), O(n+100), O(n+log(n)) usw.



Falsch ausgedrückt, ich weiss es gibt ein O und ein Theta was aussieht wie ein O mit Strich in der Mitte. Letzteres handelt sich dann wohl um den exakten Aufwand. Ich wollte das nur der Vollständigkeit halber dazugesagt haben.

Dass dies alles wie du sagst in der selben Menge liegt, denke ich habe ich klar gemacht. Nicht jedoch z.b. O(n * log(n)). Der kleine aber feine Unterschied


----------



## langhaar! (1. Feb 2012)

xKoRe hat gesagt.:


> Falsch ausgedrückt, ich weiss es gibt ein O und ein Theta was aussieht wie ein O mit Strich in der Mitte. Letzteres handelt sich dann wohl um den exakten Aufwand.



Sorry, wieder falsch.
Auch das Theta ist nicht der exakte Aufwand; es beschreibt eine Klasse von Aufwänden in einem bestimmten Bereich, die asymptotisch gleich sind. Das hat mit exaktem Aufwand nichts zu tun.

3n +4 ist nicht n/2. Trotzdem liegen beide asymptotisch im Bereich Theta(n).


----------



## Xpisto (1. Feb 2012)

Hey Leute, was sagt ihr eigentlich zu der folgender Aussage:


Algorithmen mit einer Laufzeit von O(n^k) werden als effizient bezeichnet? Dabei steht k für eine Konstante.


----------



## XHelp (1. Feb 2012)

Was sagst du zu der Aussage:
Beton ist ein leichtes Material?
Wenn du es mit Eisen vergleichst - dann ja, wenn du es mit Holz vergleichst, dann nicht :bahnhof:


----------



## Xpisto (1. Feb 2012)

Also sind es keine effiziente algorithmen hab ichs richtig angekreuzt ja?


----------



## HimBromBeere (1. Feb 2012)

Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...

guckst du hier: http://www.java-forum.org/java-basics-anfaenger-themen/131011-schleifen-o-notation-3.html#post858724

EDIT: 


> Also sind es keine effiziente algorithmen hab ichs richtig angekreuzt ja?


Ja, haste fein gemacht:toll:


----------



## Xpisto (1. Feb 2012)

Wunderbar 

Ich möchte mich nochmal recht herzlich bei euch bedanken für alle hilfreichen Antworten. Mal schaun obs mich bei der Klausur weitergebracht hat


----------



## XHelp (1. Feb 2012)

Ich finde nach wie vor, dass die Aussage falsch ist. Ist 40 eine große Zahl? Sind 5 Tage eine große Zeitspanne? Sind 30 cm lang?


----------



## Xpisto (1. Feb 2012)

Ja es war doch eine ankreuzfrage die mit wahr oder falsch beantwortet werden musste undich hab falsch angekreuzt, Algorithmen mit O(n^k) sind nicht effizient.

Oder was meinst du jetzt?


----------



## HimBromBeere (1. Feb 2012)

Ich gebe XHelp recht, dass die Aussage eigtl. nicht mit richtig oder falsch beantwortet werden kann, da es einer Relation bedürfte. Es müsste vielleicht eher heißen: solche Algorthmen GELTEN als ineffizient (da es durchaus theoretisch auch NOCH schlimmer geht).
Aber wie ich bereits erwähnt hab ist O(n^k) schon wirklich mies und sollte vermieden werden, soweit dies möglich ist.


----------



## Xpisto (1. Feb 2012)

HimBromBeere hat gesagt.:


> Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...



Ehm da wollt ich jetzt doch n ochmal nachhaken, du sagst es gibt keine effizienzklasse die schlechter ist? Dabei wäre doch O(n³) schlechter als O(n²). Beide sind doch O(n^k) oder nicht?


----------



## HimBromBeere (1. Feb 2012)

> Ehm da wollt ich jetzt doch n ochmal nachhaken, du sagst es gibt keine effizienzklasse die schlechter ist? Dabei wäre doch O(n³) schlechter als O(n²). Beide sind doch O(n^k) oder nicht?


O(n³) ist natürlich schlechter als O(n²). Aber nach der exponentiellen Effizienzklasse kommt halt nicht mehr viel, das sollte damit gemeint sein...

EDIT: Bevor mich noch jemand in die Pfanne haut: k >= 2


----------



## Xpisto (1. Feb 2012)

Ja richtig, also das wird schon gepasst haben. Dank dir


----------



## Paddelpirat (1. Feb 2012)

Moment mal. O(n^k) für k konstant ist doch polynomiell und gilt somit (in Relation zu exponentiellen Laufzeiten, also O(k^n) für k konstant und n variabel) als effizient.


----------



## XHelp (1. Feb 2012)

Paddelpirat hat gesagt.:


> und gilt somit (in Relation zu exponentiellen Laufzeiten, also O(k^n) für k konstant und n variabel) als effizient


Ja, aber in Relation zu O(log(n)) ineffizient. Es kommt eben darauf an was du womit vergleichst.
Oder mal ein ganz anderes Beispiel: wenn du es schaffst ein NP-schweres Problem (z.B. Clique in Graphen) in O(n^k) zu lösen, dann ist a) diese Laufzeit SUPER effizient und b) du ein SUPER reicher Mann.


----------



## Paddelpirat (1. Feb 2012)

Deswegen habe ich auch in Relation geschrieben.  
Die Frage, so wie sie hier steht ist unpräzise gestellt und die Antwort hängt meiner Meinung nach von dem Kontext und der Vorlesung ab. Wenn man da zwischen Algorithmen mit polynomieller und exponentieller Laufzeit unterschieden hat, dann könnte man schon erwarten, dass man O(n^k) für k konstant, als polynomielle Laufzeit erkennt. 

Und so wie ich HimBromBeeres letzten Post lese, scheint er/sie unter n^k für (konstantes k) exponentielle Laufzeit zu verstehen. Das ist aber so nicht richtig, da es polynomiell ist.

Edit zu NP: Sorry, ich erkenne gerade nicht den Zusammenhang *g*. Habe auch nicht vor P=NP oder P!=NP zu zeigen, da zerbrechen sich schon genügend andere den Kopf drüber. So wie ich es aus meinen Vorlesungen kenne soll man vom Aufgabentyp her zeigen, dass man den Unterschied zwischen O(n^k) und O(k^n) verstanden hat. Aber ich stimme dir zu, die Frage ist unpräzise


----------



## HimBromBeere (1. Feb 2012)

Oooooh, tschuldigung, das hab ich tatsächlich komplett übersehen... ich bin (weiß der Kuckuck warum) von k^n ausgegangen und nicht n^k). Ja, mit n^k bewegen wir uns wirklich in einer Grauzone, die ziemlich ungenau zu definieren ist. Die Aufgabenstellung ist tatsächlich doof formuliert, ich meine mit 





> Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...


natürlich k^n, das ist schon so ziemlich Wurst-Käse.

Tschuldigung für die Verwirrung

EDIT: mal für Fach-Informatiker: Was ist NP?


----------



## XHelp (1. Feb 2012)

HimBromBeere hat gesagt.:


> mal für Fach-Informatiker: Was ist NP?


Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit gelöst werden können :joke: Hört sich abgefahren an, aber im Grunde sind es Probleme, die "normal" (determenistische Turingmaschine) eine exponentielle Laufzeit haben. Ist eine Komplexitätsklasse von Problemmen in der theoretischen Informatik. wiki. Es ist aber nichts, was man so kurz und knapp komplett erklären könnte.
Und was meine Anspielung auf "SUPER reich" angeht: Es gibt auch eine Klasse P, die eben "normal" eine polynomielle Laufzeit hat. Es ist nach wie vor nicht bewiesen, ob es dabei um die selben Klassen handelt, oder ob P eine Untermenge ist (wiki). Es ist eins der Millennium-Probleme, für die Lösung welcher man 1 Million Dollar kassiert. Darüber hinaus hätte man so ganz nebenbei gezeigt, dass man egal welches lösbares Problem in polynomieller Laufzeit lösen kann (wie z.B. das Knacken der PIN, oder Militärverschlüsselung  ), dann werden die Hacker-Filme mit "klick, klick, klick - wir sind in Pentagon" plötzlich zur Wirklichkeit 
_(man geht stark aber davon aus, dass P!=NP ist)_


----------



## HimBromBeere (1. Feb 2012)

Oooooookay... ich hab das wiki gelesen und annähernd nichts verstanden???:L... aber sei´s drum, es gibt Dinge, die muss man nicht verstehen. Ist auch Wurscht...


----------



## Paddelpirat (1. Feb 2012)

Eine Komplexitätsklasse in der einige interessante Problemstellungen liegen, wie das von XHelp erwähnte.
Es ist auch ein NP-schweres Problem (durch Reduktion zu zeigen). Wenn ein Problem NP-schwer ist und in NP liegt, heißt es NP-vollständig.

Für diese Probleme gibt es bisher keine effizienten (sprich polynomielle) Algorithmen. Würde man zu einem Problem einen effizienten Algorithmus finden, hätte man für all diese Probleme einen effizienten Algorithmus.

So das nur mal ganz grob. Hier gibts mehr: NP (Komplexitätsklasse) ? Wikipedia

Falls du dich noch mehr dafür interessierst, kannst du auch mal nach Satz von Cook / SAT / 3-SAT umgucken.

Edit: 





XHelp hat gesagt.:


> Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit gelöst werden können



Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit "akzeptiert" werden. :bae:. Ich geh glaub ich besser gleich mal schlafen. Hatte nur im November meine Prüfung und musste das können.


----------



## JustGuest123 (15. Feb 2012)

Moin Leute, auch mal eine kurze Frage, da es thematisch hier reinpasst. Habe online folgendes Beispiel gefunden, das mir spontan auch nicht einleuchtet. Abgesehen von der etwas wirren Zählerbezeichnung müssten meiner Auffassung nach bei Schleifen aus O(k²) sein. entnommen hier: O-Notation

bitte um kurze Info/Input. Danke&Gruß

Beispiele:

for (i = 0; i < k; i++) {             for (i = 0, i < k; i++) {
   for (j = 0; j < k; j++) {             for (j = 0; j < k; j++) {
      brett_[j] = 0;                      if (a == a[j]) treffer = true;
   }                                     }
}                                     }

k2 Schritte für k2 Daten 	k2 Schritte für k Daten
O(n) -Algorithmus 	  	O(n2) -Algorithmus_


----------



## SlaterB (15. Feb 2012)

O(k^2), korrekt, das steht dort doch auch mehr oder weniger,
es ist nur die Frage als was man n ansieht, ist n == k, dann O(n^2), ist n aber k^2 dann offensichtlich O(n)

bei dem 2D-Array wird die gesamte Datenmenge als n aufgefasst,
stell dir vor es wäre nur ein Array mit entsprechend höhere Länge, die Schleife durchläuft jedes Datenfeld genau einmal, 
linear zur (auf Kantenlänge bezogen quadaratischen) Gesamtgröße


----------



## JustGuest123 (17. Feb 2012)

Moin,
erstmal vielen Dank. Hätte noch eine weitere Frage:

Countingsort: Countingsort ? Wikipedia

Mir leuchtet intuitiv nicht ein, wieso die Laufzeit dort so ist wie sie angegeben ist (O(n+m)) Wenn ich mir den Javacode anschaue:

die erste for-Schleife sucht aus dem Eingabearray int[] numbers die größten wert. Das ist ja eigentlich O(n) wenn n=length.numbers ist

das Zählen wie oft jede Zahl vorkommt auch O(n)

bei den nächsten beiden Schleifen bin ich nicht 100% sicher. die innere müsste eigentlich m sein (Anzahl aller Zahlen aufsummiert, dies wird hier wohl mit m bezeichnet). Das soll dann O(m) sein?

insgesamt ist das ja dann eigentlich schon O(n+n+m)? und vor allem, was ist mit der dritten for-schleife? unter den Teppich gekehrt? Letztendlich haben wir hier ja dann eine lineare Laufzeit mit irgendeiner Konstante...oder?

Danke für Input.


----------



## Sonecc (17. Feb 2012)

Wenn meine Erinnerung mich nicht trügt (ist nun schon 4 Jahre her seit ich das hatte), sollten konstanten in der o-notation vernachlässigt werden.
Das bedeutet bei deinem Beispiel:

O(n+n+m) = O(2n+m) <=> O(n+m)


----------



## SlaterB (17. Feb 2012)

Konstante ist ein gutes Stichwort, Konstanten sind eben hierbei egal,
es gibt Schleifen über n und Schleifen über m, deswegen gehen beide linear ein,
wenn man an n = 100, 100 Mio. oder 100 Mrd. denkt ist es ziemlich egal ob es eine oder 4 Schleifen sind, Konstante Faktoren fallen immer weg,

nur quadratisch oder log wäre eine wichtige neue Ordnung,
n^2 wird irgendwann immer größer, egal wie hoch die Konstante eines linearen Aufwands ist


----------



## JustGuest123 (18. Feb 2012)

Danke Leute, wirklich hilfreich. Schönes WE


----------

