O- Notation, Frage zu Codeschnipsel (Peseudocode)

[sh33p]

ich habe einen kleinen Codeschnipsel und möchte anhand der O-Notation die Laufzeit abschätzen. Die Laufzeit soll hier O(n) sein. Begründung ist: "Weil die maximale Rekursionstief n+1 ist".
Kann mir das jemand mal bitte erklären?
(ein block stellt eine Methode dar)

[Java]

block bhochn(ein: b € N, n € N aus: erg € N)
{
falls n = 0 dann{
erg <- 1;
} sonst{
bhochn(b,n-1, erg);
erg <- erg*b;

}

}

[/code]

 

[XHelp]

Naja, du berechnest ja b^n
b^5 wären b*b*b*b*b, daher "n" Schritte.
+1 kommt durch den Rekursionsabbruch

falls n = 0 dann

, sprich du würdest 5 mal die Rekursion durchlaufen, dann das 6. mal starten und es kommt zum Abbruch

 

[sh33p]

wie sieht es mit diesem algorithmus aus? eine andere variante bhochn auszurechnen.
hier soll die laufzeit O(log n) sein.
oberes beispiel kann ich mittlerweile nachvollziehen.

block bhochn(ein: b € N, n€ N, aus: erg€ N)
{
falls n= 0 dann {
erg <-1;
} sonst{
falls n mod 2 = 0 dann {
bhochn(b*b, n div 2, erg);
} sonst{
bhochn(b,n-1,erg);
erg <- erg*b;
}
}
}

 

[XHelp]

du rechnest die zahl immer durch 2.
log_2(x) gibt dir an die oft du die zahl durch 2 Teilen kannst, oder anders gesagt:
a^b=x
log_a(x)=b

 

[sh33p]

ah so langsam steig ich dahinter.wenn ich noch ne frage habe melde ich mich.

danke erstmal

 

[sh33p]

man könnte doch sagen,dass die laufzeit 2*ld n wäre, da bei jedem 2. durchlauf halbiert wird.
da es in der O-Notation keine Konstanten gibt, ist es einfach O(log n)
?!

 

[XHelp]

Öhm, ich denke schon, wobei da noch das "+1" ist wegen dem rekursionsabbruch.