czy prawdziwe jest to szacowanie? moglby ktos mi to wyjasnic i uzasadnic?
\(\displaystyle{ 2^{n}}\) +\(\displaystyle{ \log (2)n}\)=0(\(\displaystyle{ 2^{n}}\))
notacja O
-
- 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
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.
\(\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.