O-Notation

  • Hulli, irgendwie habe ich leider noch nicht verstanden, wie man die O-Notation bei einem Algorithmus herausfindet.



    Können wir mal die Methoden durchgehen?


    1.) Verstehe absolut nicht... warum berechnet Quadratwurzel, und wieso ist es O(Wurzel(n) .
    Er geht die while-Schleife durch und erniedrigt dabei n immer mehr. ja und?:D


    2.)


    Dass es das Quadrat berechnet ist klar, aber wieso ist die Laufzeit o(n) ?
    While Schleife wid n mal durchlaufen, dabei macht es eine mathematische Operation (ist diese denn wichtig bzw. zu beachten bei der Laufzeitangabe??) ... und nu?




    3.)



    n-1 mal die schleife, dann n immer halbiert... auch keine ahnung wie man auf O(log2*n) kommt


    So erstmal die drei, kann mir das einer von den Meistern Yodas hier helfen ? :devil:



    thxschonmal ciao

  • 1. Überleg dir einen geschlossenen Ausdruck für t(i) - also den Wert t in der i-ten Iteration.


    2. Wenn eine einzige Schleife n-mal durchlaufen wird, ist es trivialerweise O(n)


    3. Das sollte eigentlich klar sein, wenn du weißt, was ein Logarithmus ist.


    z.B.
    4>n<=8, Schleife 3mal
    8>n<=16, Schleife 4mal
    16>n<=32, Schleife 5mal
    usw.

  • Für die O-Notation rechnest du dir einfach aus, wieviele Berechnungen (maximal) angestellt werden müssen in Relation zur Eingabe. Konstante Faktoren fallen dabei raus, d.h. ob du n, 2n oder 3n Berechnungen durchführst, weil in einer Schleife, die n mal ausgeführt wird, 1, 2 oder 3 Berechnungen vorkommen, ist egal. O(2n+1) ist dasselbe wie O(n).


    Im Normalfall reichts einfach aus nachzuschaun, wie oft die innerste Schleife (bzw. der innerste Funktionsaufruf) eines Algorithmus insgesamt durchgeführt wird und du kommst auf die O-Notation, zumindest bei solchen einfachen Beispielen.

    "Sausen Sie mit mir ins Laplace-Land" - KAISER 4ever :D

  • Okay, danke euch...aber auf dem O(wurzel(n)) würde ich jetzt immer noch nicht kommen, egal. also logarithmisch immer dann, wenn die eingabe halbiert wird in der schleife?


    ok, nun die nächsten, mit denen ich wieder übrhaupt nicht klarkomme:


    Code
    1. /**
    2. * 4.) berechnet Wurzel vom Quadrat von n. O(n) zunaechst Quadrat, dann daraus die
    3. * Wurzel n+Wurzel(n^2)=n+n --> O(n)
    4. */
    5. static int d(int n) {
    6. return a(b(n));
    7. }

    Hmm, d.h. wenn ich ne Methode in einer anderen Methode aufrufe, werden die Laufzeiten einfach addiert? Dann war dies doch nicht so schwer.



    Code
    1. /**
    2. * 5.) berechnet Quadrat von Wurzel n. O(n) zunaechst Wurzel, dann davon das
    3. * Quadrat Wurzel(n)+Wurzel(n)=2*Wurzel(n) --> O(Wurzel(n))
    4. */
    5. static int e(int n) {
    6. return b(a(n));
    7. }

    wie komme ich auf 2*wurzel(n) ? (woher kommt überhaupt dieses 2* ?)
    dachte: wurzel(n) + (wurzel(n))^2 und das wäre ja wurzel(n)+n ... O(n) ?
    blicke ich leider nicht durch



    Code
    1. /**
    2. * 6.) berechnet Wurzel vom Logarithmus von n. O(log2(n)) zunaechst Logarithmus,
    3. * dann daraus die Wurzel log2(n)+Wurzel(log2(n))<2*log2(n) --> O(log2(n))
    4. */
    5. static int f(int n) {
    6. return a(c(n));
    7. }

    wieso ist denn log2(n)+Wurzel(log2(n)) kleiner als 2*log2(n) --> O(log2(n))


    wenn ich z.b. für n=100 in den Taschenrechner eingebe ist 2*log2(n) nicht kleiner... (woher kommt wieder 2* ??)




    Code
    1. /**
    2. * 7.) berechnet Wurzel von n + Logarithmus von n. O(Wurzel(n)), da
    3. * Wurzel(n)+log2(n)<2*Wurzel(n)
    4. */
    5. static int g(int n) {
    6. return a(n) + c(n);
    7. }


    2*Wurzel(n) steigt schneller als log2(n) ? und auch hier: woher kommt 2*wurzel(n) , wieso nicht nur Wurzel(n) ?



    hui.. bisschen viel geworden... hoffe jemand hilft mir hierbei


    dankööö :wave: