Hulli, irgendwie habe ich leider noch nicht verstanden, wie man die O-Notation bei einem Algorithmus herausfindet.
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);
}
}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.)
/**
* 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;
}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.)
/**
* 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++;
}
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
