Wie kann man die O-Notation herausfinden (O(log(n)))?

Question

Frage:

Wir müssen hier die O-Notation herausfinden von diesem Code? Im Unterricht haben wir nur immer ganz klare gelöst, wie geht man hier überhaupt vor?

Code (java):

int i = n;

while(i>0){

i = i /2;

}

Answer 1

Wenn du \(n\) verdoppelst, dann erhöht sich die Anzahl der Iterationen um 1 (es muss ja ein mal mehr halbiert werden).

Anders formuliert, wenn du eine Iteration mehr machst, dann kannst du damit doppelt so große \(n\) verarbeiten. Diese Eigenschaft ist eine bekannte Eigenschaft der Exponentialfunktion. Die Zuordnung

        \(\text{Anzahl Iterationen} \to n\)

ist also exponentiell. Die Funktion

        \(n\to\text{ Anzahl Iterationen}\)

ist die Umkehrfunktion, also logarithmisch.

Comments

Guten Tag oswald

Danke vielmals. Das heisst hier muss man dies wirklich ausprobieren oder gibt es hier etwas auf man sich achten kann?

Kann ich hier zum Beispiel eine Rekursionsgleichung aufstellen?

Vielen Dank!

LG
Info

---

Kann ich hier zum Beispiel eine Rekursionsgleichung aufstellen?

\(T(n) = 1 + T(n/2)\)