Laufzeit eines Algorithmus mittels Big Theta bestimmen

[gamma21]

Ich bräuchte Hilfe/Bestätigung zur Laufzeit folgendes Pseudocodes:

x <-- 4*n
y <-- 0

   while x>0
       x <-- [x/2]
       for i=1,....,n
          y<-- y+x*i

Ich würde sagen der Code hat eine Laufzeit von Θ (n²). Kann mir das wer bestätigen?

 

[httpdigest]

n * log2(n)

Die innere Schleife hat immer `n` Iterationen.
Die äußere Schleife teilt x immer durch 2 und läuft, solange x > 0.

 

[gamma21]

Danke für deine Hilfe.... wie komme ich aber in der äußeren Schleife auf log2(n)? Habe nun schon öfters in der Laufzeit eine log Funktion gesehen, kann mir aber nicht ganz erklären wie man auf diese kommt. Bin auch für hilfreiche Links dankbar.

 

[Flown]

Habe nun schon öfters in der Laufzeit eine log Funktion gesehen, kann mir aber nicht ganz erklären wie man auf diese kommt. Bin auch für hilfreiche Links dankbar.

Wenn du jedes mal die Hälfte von der Hälfte, .... nimmst, ist das nun mal die Logfunktion da sie die Umkehrung von 2^x ist (denn das wäre das Doppelte vom Doppelten, ...).

 

[gamma21]

Danke für die Antwort! Das ist eine gute Erklärung!

 

[Flown]

Danke für die Antwort! Das ist eine gute Erklärung!

Das ist nur sehr salopp ausgedrückt andere haben das ein wenig formaler beschrieben, wie in Wikipedia.