LaUFZEITBerechnung

[Merlin]

BSP.:
wELCHE Laufzeit in Theta-Notation für n hat folgendes Programme?

n = 2^k
für i=1,....k {
sum = sum + 2^k + n;
}
Die Lösung von yucrems Homepage ist folgende:

Laufzeit = Theta(1)

Müsste es nicht ln(n) sein ?

[g3nfox]

Die Laufzeit hängt in diesem fall von k ab und nicht von n.
Deswegen Theta (1).
Möge mich jemand ausbessern, falls das Müll ist, was ich sage.

[Plantschkuh!]

g3nfox hat recht. Als ich AlgoDat 1 gemacht habe (Sommer 2001 oder so), hatten wir ein solches Beispiel in der Übung, mit ewig langen Diskussionen auf der Sides-Mailingliste.
Ja, n wird gleich zu Anfang des Programms mit einer Konstanten überschrieben, die weitere Laufzeit hängt nicht vom ursprünglichen Wert von n ab. Das ist ein voll blödes Beispiel, aber ich denke, diese Antwort wollen sie hören.

[Georg Kraml]

Müsste es nicht ln(n) sein ?

Auf keinen Fall. Da hier ja eine Zuweisung vorliegt, hängt n von k ab und nicht k von n.

.

[Georg Kraml]

ich denke, diese Antwort wollen sie hören.

Genau so ist es.

.