O Notation verständlich erklären?

[Miaming]

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

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 bitte sagt mir einer dass das richtig war ? würde mich zumindest iwo freuen ^^

 

[sheel]

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 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 genommen hätte, 4*3, wären 12 Durchläufe statt 40 gewesen.
Das ist schon mehr daneben.

 

[Miaming]

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² + 5n^4 +6
und ein g = 8n^4

Geben Sie für jede Kombination von f und g an, ob f = O(g) gilt. Geben Sie
zum Nachweis, dass f = O(g) gilt, eine entsprechende Ungleichung mit den
zugehörigen Werten für k und n0 an (f ? k*g, 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

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" ? ^^