Beiträge von RunTex

RunTex

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

/**
   * 4.) berechnet Wurzel vom Quadrat von n. O(n) zunaechst Quadrat, dann daraus die
   * Wurzel n+Wurzel(n^2)=n+n --> O(n)
   */
  static int d(int n) {


    return a(b(n));
  }

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

/**
   * 5.) berechnet Quadrat von Wurzel n. O(n) zunaechst Wurzel, dann davon das
   * Quadrat Wurzel(n)+Wurzel(n)=2*Wurzel(n) --> O(Wurzel(n))
   */
  static int e(int n) {


    return b(a(n));
  }

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

/**
   * 6.) berechnet Wurzel vom Logarithmus von n. O(log2(n)) zunaechst Logarithmus,
   * dann daraus die Wurzel log2(n)+Wurzel(log2(n))<2*log2(n) --> O(log2(n))
   */
  static int f(int n) {


    return a(c(n));
  }

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

/**
   * 7.) berechnet Wurzel von n + Logarithmus von n. O(Wurzel(n)), da
   * Wurzel(n)+log2(n)<2*Wurzel(n)
   */
  static int g(int n) {


    return a(n) + c(n);
  }

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:

RunTex

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

Code

public class komplex {


  /**
   *1.)  berechnet die ganzahlige Quadratwurzel von n. O(Wurzel(n))
   */
  static int a(int n) {


    int t = 1, z = 0;


    while (n > 0) {
      n -= t;
      t += 2;
      z++;
    }


    return z;
  }


  /**
   * 2.) berechnet das Quadrat von n. Laufzeit O(n)
   */
  public static int b(int n) {


    int i = 0;
    int b = 1;


    while (++i < n)
      b = b + 2 * i + 1;


    return b;
  }


  /**
   * 3.) berechnet den ganzahlige Logarithmus dualis von n. O(log2(n))
   */
  static int c(int n) {


    int z = 0;


    while (n > 1) {
      n /= 2;
      z++;
    }


    return z;
  }


  /**
   * 4.) berechnet Wurzel vom Quadrat von n. O(n) zunaechst Quadrat, dann daraus die
   * Wurzel n+Wurzel(n^2)=n+n --> O(n)
   */
  static int d(int n) {


    return a(b(n));
  }


  /**
   * 5.) berechnet Quadrat von Wurzel n. O(n) zunaechst Wurzel, dann davon das
   * Quadrat Wurzel(n)+Wurzel(n)=2*Wurzel(n) --> O(Wurzel(n))
   */
  static int e(int n) {


    return b(a(n));
  }


  /**
   * 6.) berechnet Wurzel vom Logarithmus von n. O(log2(n)) zunaechst Logarithmus,
   * dann daraus die Wurzel log2(n)+Wurzel(log2(n))<2*log2(n) --> O(log2(n))
   */
  static int f(int n) {


    return a(c(n));
  }


  /**
   * 7.) berechnet Wurzel von n + Logarithmus von n. O(Wurzel(n)), da
   * Wurzel(n)+log2(n)<2*Wurzel(n)
   */
  static int g(int n) {


    return a(n) + c(n);
  }


  /**
   * 8.) berechnet Quadrat von quadrat von n. O(n^2)
   *
   * n+n^2<2*n^2 --> O(n^2)
   */
  static int h(int n) {


    return b(b(n));
  }


  /**
   * 9.) berechnet Wurzel n mal Wurzel n. O(n)
   * Wurzel(n)+Wurzel(n)*Wurzel(n)=Wurzel(n)+n<2*n --> O(n)
   */
  static int i(int n) {


    int z = 0;
    int y = a(n);


    for (int i = 1; i <= y; i++)
      z += a(n);


    return z;
  }


  /**
   * 10.) berechnet Wurzel n mal Wurzel n. O(n) Wurzel(n)*Wurzel(n)*2=2*n --> O(n)
   */
  static int j(int n) {


    int z = 0;


    for (int i = 1; i <= a(n); i++)
      z += a(n);


    return z;
  }


  /**
   * Hauptprogramm
   */
  public static void main(String argv[]) {


    int n;


    do {
      n = IO.readInt("Eingabe von n: ");
    }
    while (n < 1);


    IO.print("a(" + n + ") =");
    IO.println(a(n), 8);


    IO.print("b(" + n + ") =");
    IO.println(b(n), 8);


    IO.print("c(" + n + ") =");
    IO.println(c(n), 8);


    IO.print("d(" + n + ") =");
    IO.println(d(n), 8);


    IO.print("e(" + n + ") =");
    IO.println(e(n), 8);


    IO.print("f(" + n + ") =");
    IO.println(f(n), 8);


    IO.print("g(" + n + ") =");
    IO.println(g(n), 8);


    IO.print("h(" + n + ") =");
    IO.println(h(n), 8);


    IO.print("i(" + n + ") =");
    IO.println(i(n), 8);


    IO.print("j(" + n + ") =");
    IO.println(j(n), 8);
  }
}

Alles anzeigen

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

Code

/**
   * 2.) berechnet das Quadrat von n. Laufzeit O(n)
   */
  public static int b(int n) {


    int i = 0;
    int b = 1;


    while (++i < n)
      b = b + 2 * i + 1;


    return b;
  }

Alles anzeigen

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

Code

/**
   * 3.) berechnet den ganzahlige Logarithmus dualis von n. O(log2(n))
   */
  static int c(int n) {


    int z = 0;


    while (n > 1) {
      n /= 2;
      z++;
    }

Alles anzeigen

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