Funktion und O-Notation

Neue Frage »

Auf diesen Beitrag antworten »
Vogel007 Funktion und O-Notation

hi, könnt ihr mir helfen f(n) zu bestimmen, sodass ich die O-Notation angeben kann?

... also habe f(n)= 2*f(n-2) gegeben, daraus habe ich diese tabelle erstellt


n 1--2--3--4--5--6--7--8---9--10---11--12
--------------------------------------------------
f(n) 1--1--2--2--4--4--8--8--16--16--32--32


... nun muss ich aus dieser tabelle schließen, wie f(n) nun von neuem aussieht.
Ich bekomme das einfach nicht hin, probiere schon seit stunden rum

Einige sagen es hat was mit runden zu tun, aber wie soll man das denn hinschreiben??


---------------------------------------------------------------------------
-------
Beispiel: ich habe f(n)=2*f(n-1) gegeben, tabelle dazu :

n 1--2--3--4---5---6-----7--- 8
--------------------------------------
f(n) 1--2--4--8--16--32---64---128

daraus kann man lesen : f(n) = 2^(n-1) ... hierdrauß kann ich dann die O-Notation rauskriegen und beweisen (mit vollst. Induktion).


ciaoo
 
Auf diesen Beitrag antworten »
Tobias

[latex]f(n) = 2^{\left\lfloor \frac{n-1}{2} \right \rfloor}[/latex]
Auf diesen Beitrag antworten »
Vogel007

hmm, man muss ja runden, damit es immer klappt. ich weiß nicht... kann ich jetzt damit einfach die O-notation angeben und die auch mit der induktion beweisen?

O-Notation ist hier doch O(2^n) ?


ciao
Auf diesen Beitrag antworten »
Tobias

O-Notation ist vieles. Z.B. auch [latex]O(n^n)[/latex] oder [latex]O(n!)[/latex].

[latex]O(2^n)[/latex] ist mit Sicherheit richtig. Aber auch [latex]O(2^{\frac{n}{2}}) = O(\sqrt{2^n})[/latex]
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »