Laufzeit Berechnung Groß O Notation

18.02.2017, 13:28	Auf diesen Beitrag antworten »
Ghorki	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?


18.02.2017, 15:07	Auf diesen Beitrag antworten »
eulerscheZahl	Potenzgesetze: $[latex]2^{\sqrt{\log_2(n)}} = 2^{\log_2(n)^{1/2}} = n^{\frac{1}{2}} = \sqrt{n}[/latex]$
18.02.2017, 15:40	Auf diesen Beitrag antworten »
Ghorki	Hi danke schonmal, aber warum liegt es dann nur in Omega und nicht noch in den anderen?
19.02.2017, 16:33	Auf diesen Beitrag antworten »
Ghorki	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.
Anzeige

23.02.2017, 01:00	Auf diesen Beitrag antworten »
taytm	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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »