0 Daumen
280 Aufrufe

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;

}

Avatar von

1 Antwort

0 Daumen

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.

Avatar von 5,6 k

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)\)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community