Komplexität

ufuk90 · Full Member Anmeldungsdatum: 22.10.2008 Beiträge: 155

Abend an alle,

übe grade für meine Prüfung am Mittwoch und habe bezüglich der Komplexität fragen.

Ich soll zeigen, welche der folgenden Gleichungen gelten.
Beispiel: 2^(n+1) = O(2^(n))
O = für große Werte von n "nicht stärker" wachsend wie die Funtkion g(n).

g(n) ist doch jetzt in diesem Fall 2^(n+1). , diese Funktion geht also für hohe n gegen unendlich.

wenn ich jetzt für O ausrechnen will, muss ich ja:

(2^(n+1)) /( 2^(n) machen oder ?

das würde heißen für sehr hohe n geht es ebenfalls gegen unendlich, jedoch nicht so schnell wie die Funtkion g(n). darum wächst es "nicht stärker" als die g(n) --> wahr

nun zum anderen beispiel, jetzt heißt es:

2^(2n) = O(2^(n))

gleiches Prinzip: g(n) = 2^(2n) wächst gegen unendlich für hohe n.

O = (2^(2n)) / (2^(n)) , dieses wächst ebenfalls gegen unendlich jedoch wie oben auch, jedoch nicht so schnell wie die Funktion g(n), darum wächst es doch nicht stärker --> wahr?

Im Skript des Professors ist die erste Aussage Korrekt und die zweite nicht. Kann mir einer erklären warum die zweite falsch ist ??

Bzw. rechne ich überhaupt richtig?

grüße

cyrix42 · Verfasst am: 17 Jul 2012 - 16:53:28 Titel:

Du solltest dir die Definition der Landau-Symbole ("O-Notation") noch einmal genau anschauen.

Es ist f(n) Element der Menge O(g(n)), wenn es ein n_0 und ein c>0 gibt, sodass für alle n>n_0 die Ungleichung f(n) < c* g(n) erfüllt ist.

Anders formuliert: Für ALLE genügend großen n ist der Quotient f(n)/g(n) beschränkt.

Wie schaut das mit den beiden Funktionen f(n) = 2^n und g(n) = 2^(n+1) aus? Und wie umgekehrt?

Cyrix
_________________
Die Wurzel
--