O-Notation

[HaliGali9761]

static int fct1 (intm) { return m; }
static int fct2(intm) {
inti= 0;
while(m> 0) {
m=m/2;
i++; }
return i; }
static int fct3 (intm) {
int s= 0;
for (inti= 0;i<m;i++)
s=s+i;
return s ; }

Hallo,
ich hoffe ihr könnt mir etwas auf die Sprünge helfen. Ich soll die Laufzeitkomplexitäten der Funktionen fct1,fct2 und fct3 in O-Notation angeben. Ich habe mir für fct1: O(1)(konstant), fct 2: O(n)(linear) und für fct 3: O(n)(linear) notiert, aber ich weiß selber nicht ob das richtig ist. Ich finde im Internet leider kaum hilfreiches Material zu Laufzeitkomplexitäten und würde mich freuen wenn mir jemand ein gutes Skript oder Buch spezifisch zu Algorithmen und Datenstrukturen empfehlen könnte. Über Denkanstöße würde ich mich sehr freuen!

 

[RB-Development]

bei fct1 und fct3 sehe ich das genauso.
Für fct2 sieht das Ganze ein wenig komplexer aus, wenn ich mich noch recht entsinne (Ewigkeiten her)
Hierbei muss aufgrund des Integers m gelten, dass m geteilt durch 2^x <1 ist (vorletzter Durchlauf):
m/(2^x)<1
Somit gilt für die Anzahl der Durchläufe:
x<ln(m)/ln(2)
Da wir hier den vorletzten Durchlauf berechnet haben muss für x gelten:
x=ln(m)/ln(2)
Bitte nochmal prüfen, ich habe das eben nur kurz überflogen (die Funktion Formel-einfügen habe ich leider gerade auch nicht gefunden, vll. kann mir hier ein Admin behilflich sein?)

 

[RB-Development]

EDIT: Es handelt sich natürlich um den letzten Durchlauf.

bei fct1 und fct3 sehe ich das genauso.
Für fct2 sieht das Ganze ein wenig komplexer aus, wenn ich mich noch recht entsinne (Ewigkeiten her)
Hierbei muss aufgrund des Integers m gelten, dass m geteilt durch 2^x <1 ist (vorletzter Durchlauf):
m/(2^x)<1
Somit gilt für die Anzahl der Durchläufe:
x<ln(m)/ln(2)
Da wir hier den vorletzten Durchlauf berechnet haben muss für x gelten:
x=ln(m)/ln(2)
Bitte nochmal prüfen, ich habe das eben nur kurz überflogen (die Funktion Formel-einfügen habe ich leider gerade auch nicht gefunden, vll. kann mir hier ein Admin behilflich sein?)