Beispiel 1.3

[TheWhiteRabbit]

Also A is mir einigermaßen klar.

Aber bei B weiS ich nicht wie einige Leute auf die Laufzeit: sqrt(n)+n kommen.

Folgend der Java-Code


public class Bsp3B {

public Bsp3B() {
double n = 100;
int i = 1;
int a = 1;
double x = 0;
int times = 1;

System.out.println("i: " + i);
System.out.println("Wurzel aus n " + Math.sqrt(n));

do{
i = i + 1;
a = a * 2;
times = times + 1;


}while(i < Math.sqrt(n));

System.out.println("Do-loop: "+times);

times = 1;
for(int j = 0; j < a; j++){
times = times + 1;

x = x + j;

}

System.out.println("For-loop: "+times);

}

}

[spjoe]

ich hab
deta(sqrt(n) + 2^(sqrt(n)-1))

mfg spjoe

[Ali K]

ja ich hab das eigentlich auch raus

versuch einmal eine erklärung, vl. kann wer zustimmen bzw. widerlegen:

die erste schleife (wiederhole i=....bis i >=sqrt(n)) wird sqrt(n) durchlaufen das steht auch überall einstimmig...aber da in der Schleife ja immer 2 Rechenoperationen stattfinden, ist ja der Zeitaufwand 2*sqrt(n), oda ?

und die 2. Schleife (for j=0...) die wird 2^sqrt(n) ausgeführt , also so oft wie groß das a am ende ist und das ist halt nunmal 2^sqrt(n)

heisst in summe beträgt der zeitaufwand 2*sqrt(n) + 2^sqrt(n). Dividiert man das jetzt durch 2 kommt manich auf dasselbe ergebnis wie spjoe

das würde aber bedeuten, dass ich als Laufzeit einfach 2^sqrt(n) bekomme weil ich mich ja für die ordnung der Laufzeit interessiere...Meinungen dazu ?

[onuris]

was habt ihr bei a rausbekommen?

[onuris]

Eine Frage zu b:

In Zeile 6 heißt es: bis i => sqrt(n); sollte das nicht kleiner gleich heißen.

[Lillipip]

Also ich hab:
A... Theta 2 ^ n
B... Theta sqrt(n) + n

[spjoe]

Eine Frage zu b:

In Zeile 6 heißt es: bis i => sqrt(n); sollte das nicht kleiner gleich heißen.
"bis" nicht mit "solange" verwechseln (bei bis ist das was in der klammer steht die Abbruchsbedingung!

A hab ich deta(log(n)*sqrt(n)
B hab ich deta(2^(sqrt(n))
lg spjoe

[Lillipip]

"bis" nicht mit "solange" verwechseln (bei bis ist das was in der klammer steht die Abbruchsbedingung!

A hab ich deta(log(n)*sqrt(n)
B hab ich deta(2^(sqrt(n))
lg spjoe


Wie kommst du auf A und B?

[spjoe]

Wie kommst du auf A und B?

uups bei A hab ich fehler das es ja nicht a= n sonder a =2^n ist es ja dann log zur basis 2 ist dann der aus log(2^n) = n --> deta(n*sqrt(n))

bei b ist die erste schleife sqrt(n)
die zweite schleife 2^sqrt(n)
--> deta(2^sqrt(n))

lg spjoe

[timurlan2]

kann jemand 3 bsp (a,b,c,d) besser erklären? habe schon geschaut, aber kann nicht verstehen :(

[onuris]

vielleicht hilft dir bei Beispiel a das weiter:
theta(n*log2^sqrt(n)) = n*sqrt(n) --> da log2 = 1 --> log = ld

[TheWhiteRabbit]

Hmm hätt beim ersten sowieso gesagt

A:

a = 2^n also Theta 2^n

und a hängt noch von a/2 ab

also log2(2^n)

und halt j = sqrt(n)

also sqrt(n) + log2(2^n)

wie ihr da umformt um auf das ergebniss zu kommen hab ich keinen schimmer

und beim b, äussere schleife is klar

aber meiner meinung nach is das Ganze
sqrt(n) + 2n

das is alles so verwirrend *schnüf*

[FloW07]

Ad A)

Da die For Schleife verschachtelt ist sollte man doch die Laufzeiten der einzelnen Schleifen (while & for) multiplizieren und nicht addieren !

Laufzeit der ersten Schleife (solange ...) : ld(2^n) * sqrt(n)

Und das wäre auch schon mein theta(ld(2^n) * sqrt(n)

Also jede Laufzeit einer verschachtelten Schleife wird multipliziert (und nicht addiert!) .

auf ld(2^n) komme ich weil die schleife in jedem durchgang a/2 macht und deshalb auch ld(2^n) oder was aber egal ist log2(2^n) .

[dog]

Nur so eine Frage:
Haben wir nicht in der Vorlesung gehört das für die Laufzeitberechnung die Basis de Logarithmus nicht relevant ist, oder irre ich mich da?

A)--> sqrt(n)*log(n)
B)Schleife widerhole bis i>= sqrt(n)
--> sqrt(n) laufzeit
Schleife j=0..a
das a erhalten wir aus der oberern Schleife
hier wird also sqrt(n) mal gesagt a=a*2

also hätten wir dann doch
2^(sqrt(n)) +sqrt(n)


C)
für die erste Schleife würde ich sagen: n
dann k auf n setzen

und dann k = k/2

D)
Bin ich ganz unsicher
x=sqrt(n)

und x = x-1;

[schelch]

Meine Ergebnisse (stimmen mit dem ein oder anderen hier geposteten überein):
a) n*sqrt(n)
b) 2^sqrt(n)
c) n, n, k/2
d) sqrt(n), x-1

[FloW07]

Was soll da jetzt rauskommen bei A ?


ld(2^n) * sqrt(n) oder n*sqrt(n) oder ld(n) sqrt(n) oder ist das alles dasselbe weil das nur die skalierung verändert und daher wurscht ist

[onuris]

Was soll da jetzt rauskommen bei A ?


ld(2^n) * sqrt(n) oder n*sqrt(n) oder ld(n) sqrt(n) oder ist das alles dasselbe weil das nur die skalierung verändert und daher wurscht ist


ld(2^n) * sqrt(n) = n*sqrt(n)

[lowkey]

Also bei 3.A habe ich (wurzel)n*logn:
die für schleife wird (wurzel)n mal durchgeführt da j = (wurzel)n ist. a wird logarithmisch abgebaut weil a/2 dort steht.

Bei 3.B habe ich (wurzel)n weil nur das i von n abhängt und i solange inkrementiert wird bis es (wurzel)n ereicht, das heist das ganze wird (wurzel)n mal durchgeführt.

[schelch]

Also bei 3.A habe ich (wurzel)n*logn:
die für schleife wird (wurzel)n mal durchgeführt da j = (wurzel)n ist. a wird logarithmisch abgebaut weil a/2 dort steht.
Würde stimmen wenn a=n wäre. Ist es aber nicht ^^


Bei 3.B habe ich (wurzel)n weil nur das i von n abhängt und i solange inkrementiert wird bis es (wurzel)n ereicht, das heist das ganze wird (wurzel)n mal durchgeführt.
Du ignorierst ja komplett die 2. Schleife.n bedingt i und a, daher sollte man die 2. Schleife dazuaddieren (die wird sogar ganz schön oft ausgeführt).

[lowkey]

Zu A:
Wenn ich mir das so überlege sollte es wirklich 2^logn sein, hatte gedacht die 2 wäre eine art konstante aber das stimmt dann nicht so mit dem abbau von a überein, daher stimmt ich 2^logn zu.
(wurzel)n*2^logn wäre dann die antwort

Zu B:
Das a hängt nicht von n ab was in der Angabe aber steht das man die Laufzeit in abhängigkeit von N machen soll.

[Thexman]

zu B

bin mir ziemlich sicher das hier sqrt(n)+n rauskommt, keine Ahnung was aktueller Stand is, aber sollte stimmen

is ja im prinzip nix anders wie bei D nur das hier aufsummiert und nicht reduziert wird

[iamdog]

aber das sind doch verschachtelte funktionen, bei denen man die laufzeiten normalerweise multipliziert, oder?

also eigentlich sqrt(n) * n

[Thexman]

A ist verschachtelt da kommt *
B ist nicht verschachtelt +

[michaelh]

b ist nicht verschachtelt aber a hängt davon ab wie hoch das n ist! und wir sollen ja laut angabe in abhängikeit von v in teta notation bestimmen!
wenn a eine konstante wäre wäre deine lösung richtig

[michaelh]

B)Schleife widerhole bis i>= sqrt(n)
--> sqrt(n) laufzeit
Schleife j=0..a
das a erhalten wir aus der oberern Schleife
hier wird also sqrt(n) mal gesagt a=a*2

also hätten wir dann doch
2^(sqrt(n)) +sqrt(n)




hast recht oder es wird die laufzeit mit der höchsten potenz genommen!

[Thexman]

b ist nicht verschachtelt aber a hängt davon ab wie hoch das n ist! und wir sollen ja laut angabe in abhängikeit von v in teta notation bestimmen!
wenn a eine konstante wäre wäre deine lösung richtig

ja es hängt ab, aber die laufzeiten werden addiert und nicht multipliziert is ja nicht verschachtelt

[michaelh]

ja es hängt ab, aber die laufzeiten werden addiert und nicht multipliziert is ja nicht verschachtelt

naja wenn die schleifen NICHT verschachtelt sind, dann kann mans entweder addieren die laufzeiten ODER man nimmt die HÖCHSTE laufzeit, was in diesem fall die 2. schleife wäre!
da a von n abhängig sein muss, schreiben wir 2^qrt(n) und aus! oder man mach noch + sqrt(n) dazu, wie man will!!

wie man auf 2^sqrt(n) kommt, ist eh schon geklärt oder??

lg

[Thexman]

ja in der ersten kommt sqrt(n) raus und in der zweiten n

was sqrt(n) + n ist
woraus theta n folgt

Edit: stimmt kommt doch 2^sqrt(n) raus sorry