Informatiker Board | Druckvorschau: Funktion und O-Notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Funktion und O-Notation (http://www.informatikerboard.de/board/thread.php?threadid=322)

Geschrieben von Vogel007 am 25.11.2007 um 14:19:

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

Geschrieben von Tobias am 25.11.2007 um 16:41:

$[latex]f(n) = 2^{\left\lfloor \frac{n-1}{2} \right \rfloor}[/latex]$

Geschrieben von Vogel007 am 25.11.2007 um 17:26:

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