Was macht dieses Program ?

[Guest]

Ich habe hier ein Programm von dem ich die Komplexitätsklasse ermitteln soll:

int division(int n){
int k=0;
while (n>0){
n=n/3;
k++
}
return k;
}

Wenn ich zum Beispiel 125 als n einsetze kommt 5 raus, bei 12 3,......
Aber wie steht das in bezug zueinander? ich hab erst gedacht das sind irgend wie lagrithmen oder so, kann mir jeamnd helfen???


Kann hier sowieso vielleicht mal jeamnd komplexitätsklassen und wie ich sie finde erklären???

 

[mic_checker]

Verstehst du nicht was das Prog macht oder in welcher Komplexitätsklasse es sich befindet?

Was es macht sollte ja eigentlich recht klar sein, du dividierst ne Zahl solange durch drei wie sie größer 0 ist und zählst ne Zählvariable hoch die du nachher zurückgibst....

 

[the_alien]

Was es macht sollte ja eigentlich recht klar sein, du dividierst ne Zahl solange durch drei wie sie größer 0 ist und zählst ne Zählvariable hoch die du nachher zurückgibst....

Eigentlich nur solange bis die Zahl < 1 ist.

 

[thE_29]

Jo und das Problem ist, dass das ziemlich schnell eintritt.

Sprich 0,9 = 0

 

[Roar]

Jo und das Problem ist, dass das ziemlich schnell eintritt.

Sprich 0,9 = 0

da der code mit ints arbeitet is da nix mit 0.9

 

[Guest]

Also, ich weiß jetzt was das programm macht. Also von einer Zahl solange durch drei teilen bis null rauskommt, oder? Macht das sinn (ist ja auch egal)....?

Und was ist mit der Kompexitätsklasse?? Ist di dann o(log n)??
Und ist es so dass es nur zwei komplexitätsklassen gibt? Alos binär oder linear??

2. Programm das mir dann gerade noch aufgetischt ist ist dieses:

int f(int n){
if (n==0) return 1;
int ergebnis=n;
for (int i=0;i<=n;i++)
ergebnis=ergebnis+f(n-1);
return ergebnis;
}

und das ist dann noch der Hinweis...
Hinweis: Zeigen Sie, dass f die Komplexit¨at O(n) = Pn
i=1
n!
i! hat. Begr¨unden
Sie, dass f damit in der Komplexit¨atsklasse von g(n) = n! liegt.

Und der macht mich voll fertig. Was heißt das zum Teufel (ich hatte noch nie ne mathe vl-werde aber nächstes semester damit anfangten versprochen! )


DANKE

 

[Guest]

Und was ist mit der Kompexitätsklasse?? Ist di dann o(log n)??
Und ist es so dass es nur zwei komplexitätsklassen gibt? Alos binär oder linear??

Nein, es gibt mehr. Such einfach mal im Netz....Gibt zum Beispiel noch "konstante Laufzeit", "quadratische","polynomial","exponentiell" etc. pp.

Was meinst du mit binärer Laufzeit? Meinst du damit etwa logarithmisch?

 

[mic_checker]

Sorry war eben net eingeloggt.

Zum Zweiten Prob:

Poste bitte mal die Aufgabenstellung nochmal - in deutsch

 

[Guest]

Also hier die komplette (!) Aufgaben stellung. Ich hab aber jetzt alles bis auf die letzte Teil aufgabe..

Aufgabe 3 a) Ermitteln Sie den Aufwand O(T(n)) f¨ur die unten angegebenen
Methoden und begr¨unden Sie Ihr Ergebnis.
int summation(int n){
int sum=0;
for (int i=1;i<=n;i++)
for (int j=1; j<=i;j++)
sum=sum+j;
return sum;
}
int division(int n){
int k=0;
while (n>0){
n=n/3;
k++
}
return k;
}
1
int f(int n){
if (n==0) return 1;
int ergebnis=n;
for (int i=0;i<=n;i++)
ergebnis=ergebnis+f(n-1);
return ergebnis;
}
Hinweis: Zeigen Sie, dass f die Komplexit¨at O(n) = Pn
i=1
n!
i! hat. Begr¨unden
Sie, dass f damit in der Komplexit¨atsklasse von g(n) = n! liegt.

oder einfach mal der Link (ich seh gerade das ist wieder schief gelaufen....
http://www.mathematik.uni-marburg.de/~abels/lehrveranstaltungen/sose05/piII/zettel05.pdf

 

[Serenity]

Ich habe hier ein Programm von dem ich die Komplexitätsklasse ermitteln soll:

int division(int n){
int k=0;
while (n>0){
n=n/3;
k++
}
return k;
}

Wenn ich zum Beispiel 125 als n einsetze kommt 5 raus, bei 12 3,......
Aber wie steht das in bezug zueinander? ich hab erst gedacht das sind irgend wie lagrithmen oder so, kann mir jeamnd helfen???


Kann hier sowieso vielleicht mal jeamnd komplexitätsklassen und wie ich sie finde erklären???

Ich glaube das mit Logarithmen sollte stimmen, ich würd sagen die Schleife hat die Komplexität n * log n
Grund: es hängt von n ab, die äußere Schleife läuft n mal bei der inneren wird dividiert, dh log n also insgesammt n * log n.

Jedoch bin ich mir nicht 100pro sicher.

 

[Guest]

und was macht das andere programm:

int f(int n){
if (n==0) return 1;
int ergebnis=n;
for (int i=0;i<=n;i++)
ergebnis=ergebnis+f(n-1);
return ergebnis;
}

 

[MPWal.GastweilFaulZuLogin]

Das muss irgendwas mathematisches sein... da kommt ja bei 10 schon eine wahnwitzige Zahl raus.

 

[Guest]

Und was hat das dink für ne Komplexitätsklasse?? Ich hab jetzt mal o(log n)geraten weil das ganze ja exponentiell absteigt...

Oder??

 

[Reinhold]

und was macht das andere programm:

int f(int n){
if (n==0) return 1;
int ergebnis=n;
for (int i=0;i<=n;i++)
ergebnis=ergebnis+f(n-1);
return ergebnis;
}

das programm berechnet rekursiv die funktion:

f(n) = n + ( (n+1) * f(n-1) )

Beispiel:

f(3) = 3 + ( 4 * f(2) )
f(2) = 2 + ( 3 * f(1) )
f(1) = 1 + ( 2 * f(0) )
f(0) = 1

wenn du jetzt von unten anfängst, kannst du dir die ergebnisse
per hand ausrechnen. was die komplexität betrifft, kann ich leider nix
zu sagen, ist schon so lange her... aber wenn du dir die rechte seite
anschaust, sieht das doch irgendwie schon ein bisschen nach n! aus?!

viele grüße,
reinhold