O Notation verständlich erklären?

[Miaming]

Hallöchen zusammen, hat vielleicht einer hier ein wenig mathematisches Verständnis und könnte mir irgendwie den Zusammenhang eines Quelltexts und der ONotation begreiflich machen?

Gegeben ist folgender Quelltext:

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; 
    } 
  }

Die Onotation davon ist anscheined O!

WARUM? Ich weiß es absolut nicht. Sowie ich es bisher im Netz endeckt habe stieß ich genau zu diesem Quelltext auf folgende Aussage:

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

(ist aus einem anderen Forum spielt aber auch keine Rolle, da ich es dort leider auch nicht verstehe -..-

Ich verstehe einfach absolut nicht warum es so klar ist dass man "n/2" teilen muss um irgendwie auf die ONotation zu kommen.

Das einzige was mir klar ist, ist die Tatsache dass man 10 mal die for schleife aufruft O(10) aber Konstanten werden bei der Onota ohnehin ignoriert aber nya ... gibt es hier vielleicht einen der ein bisschen plan hat?

 

[CPoly]

Ich verstehe einfach absolut nicht warum es so klar ist dass man "n/2" teilen muss um irgendwie auf die ONotation zu kommen.

Du hast die Erklärung doch zitiert

da du ja immer +2 machst

Das heißt die Schleife macht n/2 Durchläufe. Mehr ist da nicht zu erklären. Wenn du n=100 hast, dann läuft deine Schleife 50 mal durch.

Und wieso man jetzt O nimmt, anstatt O(n/2): um es sich einfacher zu machen. n ist proportional zu n/2, also nimmt man einfach n. Dadurch muss man nicht erst Nachdenken, wenn man zwei Algorithmen vergleicht.

 

[Miaming]

Hallo Cpoly! Wow die Antwort ging ja echt schnell! Und ich raff es absolut nicht warum es jedem absolut klar ist ehrlich nicht ... ich habe meine Antwort zitiert weil ich immer +2 mache richtig problem ist dass ich nicht auf die idee komme also den zusammenhang genau diesen zusammenhang zu erkennen -.-

in diesem falle habe ich für N = 10 eingesetzt .... wenn ich jetzt n/2 rechne ... wäre das folglich 5! die schleife macht doch aber keine 5 durchläufe? ....

also ich weiß nicht besser wie ich das problem genau beschreiben kann... wenn ich etwas +2 addiere, wie erklärt sich denn dann die tatsache dass ich durch n/2 teilen muss ? sorry wenn ich so dumm frage aber ich kann meine hilflosigkeit nicht anders in worte fassen ... anscheinend kann es auch nicht sooo schwer sein wenn für viele der zusammenhang so eindeutig ist ....

 

[sheel]

Hi

für n=10 geht die äußere Schleife 5 mal durch. Mit i=
1 3 5 7 9
Weil immer +2 gemacht wird.
Ist doch nicht so schwer?

Und das mit dem O, hat CPoly ja schon gut gesagt, ist einfach die Proportionalität gemeint.
Wenn für n=10 die Schleife 5 Mal durchgeht,
muss sie für O bei n=100 ungefähr 50 Mal durchgehen.
n*10 -> Durchlauf*10

Wenn man etwas so programmiert hätte, dass es bei einer n-Verzehnfachung
1000x öfter durchgeht, wäre es eben o(n^3)

Gruß

 

[CPoly]

Um das mit dem +2 nochmal auf den Punkt zu bringen:

Eine "normale" Schleife rechnet immer +1. Folglich O, weil wenn du bis 100 zählen willst, läuft die Schleife auch 100 Mal durch.

Deine Schleife rechnet immer +2. Folglich O(n/2), weil wenn du bis 100 zählen willst, läuft die Schleife nur 50 mal durch. Sie ist also doppelt so schnell. Oder umgekehrt: die Komplexität ist halb so hoch (durch 2)!




Ob die jetzt 50 mal, 49 mal oder 51 mal durchläuft, ist völlig egal. Es geht bei der O Notation um eine ungefähre Abschätzung. Da spielt das keine Rolle.

 

[Miaming]

Also ich muss sagen dass ich den Zusammenhang in sooofern schon gecheckt habe wie ich gerade anhand eurer Erklärung merke...

ich setze i=1 und für n=10

die while wird betreten für i=1 bekomme ich einen neues i von 3 raus
für i = 3 bekomme ich 5 aus für i = 5 bekomme ich 7 für i = 7 bekomme ich 9 raus danach wird die äußere schleife nicht mehr betreten da 11 < 10 nicht mehr zutrifft soweit klar

somit ist hier schon mal klar, dass die äußere schleife genau 5 mal aufgerufen wird!

mein allg problem ist quasi die herleitung also dass ich drauf kommen muss n/2 zu "erkennen" ich mein wenn ich jetzt selber einsetze 10/2 = 5 entspricht ja genau dem was ich gerade erklärt habe ja! aber nya ... ^^ ich poste mal eine andere aufgabe:

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; 
}

Könnte mir einer im groben nur das "vorgehen" erklären wie ich es zu betrachten habe? ich möchte keine lösung sondern nur wie ich an die aufgabe rangehe wie ich auf das ergebnis komme ich muss es halt selbst iwie checken ^^

 

[CPoly]

Das ist schwer hier nicht direkt die Antwort zu nennen. Weil eigentlich ist das fast einer der "Standard" Fälle, anhand derer man sich orientiert. Da sind verschachtelte Schleife, von denen zwei Stück bis n zählen. Da müssten sofort die Glocken läuten ;-)

 

[sheel]

Zum Erkenne von n/2: Wie mehrmals gesagt wurde, es ist egal.
Ob n, n/2, n*3, n/54+1...
Wichtig ist nur die Proportion.
Wenn man n mit irgendwas multipliziert/dividiert, wie ändert sich dann ca. die Durchlaufsanzahl?


Zur zweiten Aufgabe:

Äußerte Schleife: Geht zweimal durch. Egal ob n=1 oder n=1000, die geht immer nur zweimal
Da sich das mit n nicht ändert, kann man es schon vergessen.

Mittlere Schleife: Geht n-mal durch (arr.length ist ja n)
Wenn sich n verdoppelt geht die Schleife auch doppelt so oft durch. Linear.

Innerste Schleife: Das selbe: n-mal

Insgesamt: n*n
n^2


Für n=5 wird die Anweisung in der Mitte zählbar 50 Mal ausgeführt.
Wenn n jetzt verzehnfacht (n=50) wird, müsste sich die Anzahl ca. verhundertfachen (10 ^2).
Tatsächlich ist es 5000.
50 * 100 = 5000
Kommt hin.

 

[Miaming]

Ok ich muss sagen, dass ich diese zweite Aufgabe wirklich jetzt "besser" verstanden habe ^^ Die erste Schleife läuft 2 mal durch die zweite n mal (da länge n) die dritte ebenso n mal da alle scheifen ineinander verschachtelt sind hätte ich somit 2*n*n = 2n*n

Vorfaktor wird bei der Onotation ignoriert was dann n*n entsprechen würde und das ergebnis daraus wäre dann folglich n² bzw. O(n² ) soweit korrekt? das beispiel war jetzt irgendwie etwas einfacher - habt ihr vielleicht lust mich bei einer dritten aufgabe zu unterstützen ^^ ?

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

wie habe ich das jetzt zu betrachten? ich habe jetzt für n= 8 festgesetzt und dann sieht das ganze wie folgt aus:

i=1
n=8

1<8
2=1*2

2<8
4=2*2

4<8
8=2*2

somit habe ich genau 3 aufrufe soweit korrekt?

und jetzt wieder die masterfrage wie komme ich darauf jetzt auf die onotation? ich 2^3 =8 wäre meine ontation dann 2^n? O(2^n) ?

btw recht herzlichen dank schon einmal dass ihr mir helft!

 

[CPoly]

und jetzt wieder die masterfrage wie komme ich darauf jetzt auf die onotation? ich 2^3 =8 wäre meine ontation dann 2^n? O(2^n) ?

2^n wäre eine gigantische Komplexität, aber die Schleife ist ja schneller durch als eine lineare. Es ist die Umkehrfunktion von der Potenz, also der Logarithmus. O(log)


Und bei deinem Beispiel mit n = 8

log(8) [zur Basis 2] = ln(8) / ln(2) = 3 (Genau deine Anzahl der Durchläufe )