| Die letzten 4 Beiträge |
| Tobias |
O-Notation ist vieles. Z.B. auch ![[latex]O(n^n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(n^n)) oder ![[latex]O(n!)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(n!)) .
![[latex]O(2^n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(2^n)) ist mit Sicherheit richtig. Aber auch ![[latex]O(2^{\frac{n}{2}}) = O(\sqrt{2^n})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(2^{\frac{n}{2}}) = O(\sqrt{2^n})) |
| 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 |
| Tobias |
![[latex]f(n) = 2^{\left\lfloor \frac{n-1}{2} \right \rfloor}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(n) = 2^{\left\lfloor \frac{n-1}{2} \right \rfloor}) |
| 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 |
|
|
