notacja O

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
tutek0
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 7 lut 2009, o 17:14
Płeć: Mężczyzna
Podziękował: 1 raz

notacja O

Post autor: tutek0 »

czy prawdziwe jest to szacowanie? moglby ktos mi to wyjasnic i uzasadnic?
\(\displaystyle{ 2^{n}}\) +\(\displaystyle{ \log (2)n}\)=0(\(\displaystyle{ 2^{n}}\))
Rogal
Użytkownik
Użytkownik
Posty: 5405
Rejestracja: 11 sty 2005, o 22:21
Płeć: Mężczyzna
Lokalizacja: a z Limanowej
Podziękował: 1 raz
Pomógł: 422 razy

notacja O

Post autor: Rogal »

Jeśli dobrze pamiętam symbole Landaua, to jest dobre. Ale żeby nie skłamać, to polecam sprawdzić na jakiejś Wikipedii dokładną definicję.
tutek0
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 7 lut 2009, o 17:14
Płeć: Mężczyzna
Podziękował: 1 raz

notacja O

Post autor: tutek0 »

wlasnie tylko w jaki sposob to uzasadnic... mam definicje przed sobą i nie praze przekazu;/
abc666

notacja O

Post autor: abc666 »

\(\displaystyle{ \left| 2^n+log(2)n \right| \le \left|2^n+2^n \right| \\
\left| 2^n+log(2)n \right| \le 2 \left|2^n \right|}\)
Rogal
Użytkownik
Użytkownik
Posty: 5405
Rejestracja: 11 sty 2005, o 22:21
Płeć: Mężczyzna
Lokalizacja: a z Limanowej
Podziękował: 1 raz
Pomógł: 422 razy

notacja O

Post autor: Rogal »

Zgodnie z definicją masz podać stałą c i jakieś n0, tak aby zachodził warunek
\(\displaystyle{ \forall n > n_{0} f(n) < cg(n)}\).
W Twoim przypadku \(\displaystyle{ f(n) = 2^n + n \log 2}\) a \(\displaystyle{ g(n) = 2^{n}}\).
Ja bym tutaj napałowo strzelił, że c = 2 i pozostaje poszukać n0:
\(\displaystyle{ 2^{n} + n \log 2 < 2^{n+1} \\ n \log 2 < 2^{n}}\), co już dla \(\displaystyle{ n_{0} := 2}\) jest prawdą i dla większych oczywiście też. Dla upierdliwych prowadzących można sobie tej nierówności dowieść przy pomocy badania zmienności funkcji.
tutek0
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 7 lut 2009, o 17:14
Płeć: Mężczyzna
Podziękował: 1 raz

notacja O

Post autor: tutek0 »

juz analizuje, THX:*
ODPOWIEDZ