Witam, mam problem z dwoma zadaniami z algorytmów. Czy ktoś mógłby napisać jak się za to zabrać? Z góry dzięki za każdą pomoc!:)
1) Pokaż, że dla każdych dwóch stałych \(\displaystyle{ a, b}\) gdzie \(\displaystyle{ b>0}\) zachodzi: \(\displaystyle{ \left( n+a\right) ^{b} =\Theta \left( n ^{b} \right)}\)
2) Czy \(\displaystyle{ 2^{n+1} = O(2^{n})}\)?
Czy \(\displaystyle{ 2^{2n} = O(2^{n})}\)?
Złożoność algorytmu, notacja
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Złożoność algorytmu, notacja
1) zbadaj granice \(\displaystyle{ \frac{n^b}{(n+a)^b}}\) i wysnuj odpowiedni wniosek
2) \(\displaystyle{ 2^{n+1}=2\cdot 2^n}\)
\(\displaystyle{ 2^{2n}=4^n}\)
2) \(\displaystyle{ 2^{n+1}=2\cdot 2^n}\)
\(\displaystyle{ 2^{2n}=4^n}\)