Informatiker Board | Druckvorschau: Laufzeit Berechnung Groß O Notation

Geschrieben von Ghorki am 18.02.2017 um 13:28:

Laufzeit Berechnung Groß O Notation

Meine Frage:
Leider stehe ich ziemlich auf dem Schlauch, wie man Laufzeiten abschätzen kann.

1. sqrt(n) element von O(2^sqrt(log2(n)))
3. sqrt(n) element von Teta(2^sqrt(log2(n)))
3. sqrt(n) element von Omega(2^sqrt(log2(n)))

Meine Ideen:
Bei leichten Beispielen wie z.B 2^n+1 element von Teta(2^n) bin ich immer wie folgt vorgegangen:

(2^n+1)/(2^n) --> 2 (für n --> inf) also liegt es in Teta, da es nicht gegen unendlich geht.

Das ist jedoch bei solchen Abschätzungen wie oben etwas schwieriger. Gibt es eine einfache bzw bessere Vorgehensweiße?

Geschrieben von eulerscheZahl am 18.02.2017 um 15:07:

Potenzgesetze:
$[latex]2^{\sqrt{\log_2(n)}} = 2^{\log_2(n)^{1/2}} = n^{\frac{1}{2}} = \sqrt{n}[/latex]$

Geschrieben von Ghorki am 18.02.2017 um 15:40:

Hi danke schonmal, aber warum liegt es dann nur in Omega und nicht noch in den anderen?

Geschrieben von Ghorki am 19.02.2017 um 16:33:

Ok ist bereits gelöst und der Term ergibt umgeformt nicht sqrt(n).
1. geht gegen inf also liegt es nicht drin
3. geht gegen inf, also größer als 0 und liegt deswegen drin
2. ergibt sich aus 1 und 3.

Geschrieben von taytm am 23.02.2017 um 01:00:

Genau,

denn dort steht: 2^(log(n)^(1/2))

Das ist etwas anderes wie (2^log(n))^(1/2) = sqrt(n)

Potenzieren ist nicht assoziativ