| Der letzte Beitrag |
| blukyvjblubb |
Komplexität, Wachstum von Funktionen
Meine Frage:
Hallo,
ich soll die folgenden Aussagen beweisen oder widerlegen. Mir fehlt irgendwie gerade noch der Blick dafür:
a) 5*log10(n) ? O(log2(n)) wobei 10 und 2 die Basis des Logarithmus darstellen
b) (n + 2)^(2n) ? O((sqrt(n))^n)
c) Aus f(n) ? O(n) folgt 2^f(n) ? O(2^n).
d) Es existiert eine Funktion f, so dass f(n) ? O(n^(1+epsilon)) für jedes epsilon > 0 und f(n) ? omega(n) gilt.
Meine Ideen:
a) Ich kenne die Def. von Groß-Omega: O(f) := {g: IN --> IR+ | es existiert ein c > 0 und ein n0 mit n ? n0 für das gilt: g(n) <= c·f(n) }
In diesem Fall ist mein f(n)=log2(n) und mein g(n)=5*log10(n).
Z.z.: 5*log10(n)<=c*log2(n)
Dazu benutze ich die Rechenregel: loga(b)=ln(b)/ln(a)
also <=> 5*ln(n)/ln(10)<=c*ln(n)/ln(2)
<=> 5*ln(2)/ln(10)<=c
<=> c>= 1,163 (auf drei Nachkommastellen gerundet)
Meines Erachtens bedeutet das, dass egal für welches n (n ist ja verschwunden) für ein c>= 1,163 diese Aussage gilt, oder?
b) auch hier benutze ich die Definition O(f) := {g: IN --> IR+ | es existiert ein c > 0 und ein n0 mit n ? n0 für das gilt: g(n) <= c·f(n) }
In diesem Fall ist mein f(n)=(sqrt(n))^n und mein g(n)=(n + 2)^(2n).
Also (n + 2)^(2n)<= c*(sqrt(n))^n
und hier komme ich nicht so richtig weiter... n.te Wurzel auf beiden Seiten bringt mich auch nicht wirklich weiter. Wie muss man das hier richtig weiterrechnen?
c) Hier steht ja f(n)<=c1*n ==> 2^f(n)<=c2*2^n
letzteres schreibe ich um zu 2^f(n)<=2^(log(c2))*2^n = 2^(log(c2)+n)
Bei der Umformung bin ich micht ganz sicher, aber eigtl. müsste man durch Vergleich der beiden Seiten herausbekommen:
f(n)<= log(c2)+n
Und wenn man sich mal die Bedingung f(n)<=c1*n anschaut und für c1=1 und c2=1 einsetzt ergibt sich f(n)<= n ==> f(n)<= n
Was offensichtlich wahr ist. Ist meine Begründung richtig?
d) Wie ich hier vorgehe ist mir leider nicht ganz klar.
Muss ich hier eine Fkt. f(n) finden, für die gilt, dass
f(n)<=c*n^(1+epsilon) und gleichzeitig lim n-->unendlich f(n)/n=0 ???
Falls ich es richtig verstehe, könnte man hier einfach die 1-Funktion nehmen? dann gilt ja 1<=c*n^(1+epsilon) für c=1 und n0=1 und 1/n geht für n--> unendlich gegen 0.
Geht das so? |
|
|
