Mam kłopot z metodyką rozwiązywania zadań związanych z notacją O.
Do rozwiązania mam 2 przykłady:
Dla poniższych ciągów znajdź najmniejszą liczbę k taką, że \(\displaystyle{ f(n)=O(n ^{k} )}\):
a).\(\displaystyle{ f(n)=13n ^{2}+4n-73}\)
b).\(\displaystyle{ f(n)=(n ^{2}+1 )(2n ^{4}+3n-8 )}\)
Proszę o pomoc bardziej doświadczonych użytkowników.
Notacja O.
-
- Użytkownik
- Posty: 132
- Rejestracja: 1 cze 2012, o 07:04
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 15 razy
Notacja O.
\(\displaystyle{ n^k}\) od pewnego n, rośnie wolniej, niż \(\displaystyle{ }n^{k+\mbox{coś tam}}}\)
a) 2
b) 8
a) 2
b) 8
- Vardamir
- Użytkownik
- Posty: 1913
- Rejestracja: 3 wrz 2010, o 22:52
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 410 razy
Notacja O.
A trochę formalniej, zapis \(\displaystyle{ f(n)=O(n^k)}\) oznacza, że możemy funkcję \(\displaystyle{ f(n)}\) ograniczyć z góry dla pewnego \(\displaystyle{ C}\) w taki sposób:
\(\displaystyle{ f(n) \le C\cdot n^k}\)
dla dużych \(\displaystyle{ n}\). Odpowiedzi masz w poście powyżej.
\(\displaystyle{ f(n) \le C\cdot n^k}\)
dla dużych \(\displaystyle{ n}\). Odpowiedzi masz w poście powyżej.
-
- Użytkownik
- Posty: 41
- Rejestracja: 1 lis 2012, o 16:42
- Płeć: Mężczyzna
- Lokalizacja: Suwałki
- Podziękował: 22 razy
Notacja O.
Czyli bardziej szczegółowo do a) :
\(\displaystyle{ f(n)=13n ^{2}+4n-73}\)
\(\displaystyle{ 13n ^{2}+4n-73=0(n ^{k} )}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le C \cdot n ^{k}}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le 13n ^{2}+n ^{2} \le 14n ^{2}}\)
\(\displaystyle{ n ^{k}=n ^{2}, K=2.}\)
Czy powyższe jest ok ?
A jak będzie w punkcie b). ? Najpierw trzeba wymnożyć oba nawiasy?
\(\displaystyle{ f(n)=13n ^{2}+4n-73}\)
\(\displaystyle{ 13n ^{2}+4n-73=0(n ^{k} )}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le C \cdot n ^{k}}\)
\(\displaystyle{ 13n ^{2}+4n-73 \le 13n ^{2}+n ^{2} \le 14n ^{2}}\)
\(\displaystyle{ n ^{k}=n ^{2}, K=2.}\)
Czy powyższe jest ok ?
A jak będzie w punkcie b). ? Najpierw trzeba wymnożyć oba nawiasy?
-
- Użytkownik
- Posty: 41
- Rejestracja: 1 lis 2012, o 16:42
- Płeć: Mężczyzna
- Lokalizacja: Suwałki
- Podziękował: 22 razy
Notacja O.
I jeszcze proszę o podpowiedź w poniższym:
Dla każdego z poniższych ciągów podaj ciąg \(\displaystyle{ a(n)}\) taki, że: \(\displaystyle{ f(n)=O(a(n))}\).
Czy tutaj wystarczy po prostu znaleźć odpowiednie ciągi ograniczające z góry i zamienić te pierwotne?
\(\displaystyle{ f(n)=n ^{3} \cdot log _{2}n}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n =O(n ^{3} ) \cdot O(log _{2}n )}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n \le n ^{4} \cdot \sqrt[3]{n}}\)
\(\displaystyle{ a(n)=n ^{4} \cdot \sqrt[3]{n}}\)
Dla każdego z poniższych ciągów podaj ciąg \(\displaystyle{ a(n)}\) taki, że: \(\displaystyle{ f(n)=O(a(n))}\).
Czy tutaj wystarczy po prostu znaleźć odpowiednie ciągi ograniczające z góry i zamienić te pierwotne?
\(\displaystyle{ f(n)=n ^{3} \cdot log _{2}n}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n =O(n ^{3} ) \cdot O(log _{2}n )}\)
\(\displaystyle{ n ^{3} \cdot log _{2}n \le n ^{4} \cdot \sqrt[3]{n}}\)
\(\displaystyle{ a(n)=n ^{4} \cdot \sqrt[3]{n}}\)