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:

Code java:

1 2 3 4 5 6 7 8 9 10

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(n)!

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(n)

(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?

Zitat von Miaming

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(n) 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.

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

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(n), 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(n) 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ß

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

Eine "normale" Schleife rechnet immer +1. Folglich O(n), 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.

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:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

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

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.

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 ?

Code java:

1 2 3 4 5 6 7 8 9

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!

Zitat von Miaming

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(n))


Und bei deinem Beispiel mit n = 8

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

Hallo CPoly du wirst staunen auch auf den Logarithmus bin ich quasi halbwegs gekommen da ich mir gedacht habe ich hab ne 8 und die anzahl der aufrufe von 3 wie komme ich jetzt auf die 3 ... bei 2^3 = 8 ... so ich habe aber die 3 nicht gegeben also versuche ich iwie mathematisch auf ne lösung zu kommen wie ich den wert 3 erreiche?

also kann ich das als allgemeines vorgehen betrachten?

ich nehme mir ein n und zähl die anzahl der aufrufe und versuche dann rechnerisch auf die anzahl der aufrufe zu kommen?

in diesem fall siehts nämlich so aus wie du schon bereits geschrieben hast

ich habe ein n wert für 8 eine zahl der aufrufe von 3

ich überlege wie komme ich mit meinem wert 2 und 8 auf die 3 ?

2^3 = 8 da ich aber die 3 brauche benötige ich die umkehrfunktion mittels des log also log2(8) = 3

kann ich mir das als "patentrezpt" so merken ? wenn ja belästige ich euch nich mehr damit

Code java:

1 2 3 4 5 6 7 8 9 10

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

hier würde ich jetzt eine zahl der aufrufe von 4 erhalten wenn ich jetzt "meine erklärung" mal anwende habe ich wieder

n = 8
die 2 im quelltext
und als ergebnis die anzahl der aufrufe von 4

demzufolge: 8/2 = 4

meine O-notation wäre demzufolge O(n/2) ---> O(n) bitte sagt mir einer dass das richtig war ? würde mich zumindest iwo freuen

Zitat von Miaming

n = 8
die 2 im quelltext
und als ergebnis die anzahl der aufrufe von 4

demzufolge: 8/2 = 4

meine O-notation wäre demzufolge O(n/2) ---> O(n) bitte sagt mir einer dass das richtig war ? würde mich zumindest iwo freuen

Das ist eigentlich richtig, aber:
Du hast die innere Schleife vergessen

Und da die hier von der äußeren abhängt, ist es auch nicht ganz so einfach.
zB. n=8, i geht 1 3 5 7
Und für jedes i hat die j-Schleife eine andere Anzahl
i=1: 1 j-Durchgänge
i=3: 3 j-Durchgänge
i=5: 5 j-Durchgänge
i=7: 7 j-Durchgänge

"Trick" dabei: Durchschnitt
1+3+5+7 j-Durchgänge = 16
Pro i-Schleifen-Durchlauf 4
n=8, also: n/2


Äußere Schleife hat also, wie von dir schon vorher richtig erkannt, n/2
Innere Schleife hat auch n/2.
=(n^2)/4
Weg mit allem nicht-n, ergibt
O(n^2)


Wenn man durch Zählen ausprobiert, kommt man auch drauf
n zu Durchläufe
1 0
2 1
3 1
4 4
5 4
6 9
7 9
8 16
9 16
10 27
11 27
12 40

n=4 ergibt 4 Dürchläufe
O(n^2)
n=4*3 muss also 4 *(3^2) Durchläufe ergeben
n=12 hat gerechnet 36, gezählt 40
Ist nicht genau, aber verlangt ja auch keiner.

Wenn man O(n) genommen hätte, 4*3, wären 12 Durchläufe statt 40 gewesen.
Das ist schon mehr daneben.

Oh man ja du hast recht dank deiner großartigen erklärung hab ichs gecheckt .... würdest du vielleicht noch zeit finden mir ein anderes thema diesbezüglich begreiflich zu machen?

ich hab ein f(n) = n² + 5n^4 +6
und ein g(n) = 8n^4

Geben Sie für jede Kombination von f und g an, ob f(n) = O(g(n)) gilt. Geben Sie
zum Nachweis, dass f(n) = O(g(n)) gilt, eine entsprechende Ungleichung mit den
zugehörigen Werten für k und n0 an (f(n) ≤ k*g(n), für alle n ≥ n0).

kannst du mir evtl. sagen wie ich hier vorgehe? ich könnte diesmal nicht mal ein ansatz liefern da ich hiermit überfordert bin... googlen bringt bei solchen dingern nichts....

dann gibts auch so aufgabentypen wie

Gilt 7n logn = O(n)

als lösung habe ich einfach mal irgendwas mit lim n-->∞ 7n/n = lim n-->∞ = 7

oder: Gilt: n³ + 2^n = O(2^n)
Ergebnis: Die Aussage stimmt (aber wie kommt man denn drauf)

ich möchte echt nicht zuviel verlangen, nur nachdem du mir glücklicherweise halbwegs das ganze ein bisschen näher gebracht hast wollte ich dich fragen ob du hier "nochmal hand anlegen könntest" ?