Schleifen & O Notation

[Xpisto]

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]

aber da muss es doch was geben was bombensicher ist.

Zählen ?

 

[Xpisto]

Was denn zählen?

 

[njans]

      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]

Was denn zählen?

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

 

[sung]

arr[j][k] = n lauft 3*n*n Male.

 

[Xpisto]

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]

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]

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

 

[gassst]

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.

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]

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]

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]

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]

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?
*/

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; 
    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?)*/

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]

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]

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]

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]

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]

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]

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]

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

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

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]

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]

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]

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]

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

 

[Paddelpirat]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Wenn du von n bis 1 immer

/x

machst, oder von 1 bin immer

*x

. Aber "Faustregel" gibt es da nicht.

 

[Xpisto]

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]

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]

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

 

[HimBromBeere]

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]

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]

Na dann: Mut zur Lücke!

 

[XHelp]

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

 

[xKoRe]

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]

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]

Ja, auch wenn

// 10*n/2*n/2

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

 

[XHelp]

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]

Hat er doch gesagt

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

 

[XHelp]

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.