witam mam problem ze zrozumieniem zadań z dziedziny Informatyki.
1. Dla każdego z poniższych ciągów znajdź najmniejszą liczbę k, taką że \(\displaystyle{ f(n)=O(n^{k})}\) Swoją propozycję porządnie uzasadnij.
a)\(\displaystyle{ f(n)=13 n^{2}+4n-73}\)
b)\(\displaystyle{ f(n)=( n^{3}+3n-1)^{4}}\)
2. Czy poniższe zdania są prawdziwe czy fałszywe?? Uzasadnij.
a) \(\displaystyle{ 40^{n}=( 2^{n} )}\)
b) \(\displaystyle{ (2n)!=O(n!)}\)
Moze ktos to jakoś wytłumaczyć lub podać jakis opis czy cos.
zadania Algorytmy i struktury danych
-
kadiii
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
zadania Algorytmy i struktury danych
1)Korzystając z twierdzenia \(\displaystyle{ \sum_{i=1}^{k}O(a_{i}(n))=O(max{|a_{1}(n),...,|a_{k}(n)|})}\) mamy:
a)2
b)12
2)Korzystamy z defincji notacji O mamy \(\displaystyle{ f(n)=O(g(n))}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego n\(\displaystyle{ |f(n)| qslant C |g(n)|}\)
a)\(\displaystyle{ 40^{n}=O(2^{n})}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego \(\displaystyle{ n}\) \(\displaystyle{ 40^{n} qslant C 2^{n} 20^{n} qslant C}\)czyli fałsz
b) \(\displaystyle{ (n+1)! qslant (2n)!}\) \(\displaystyle{ (2n)!=O(n!)}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego \(\displaystyle{ n}\) \(\displaystyle{ (2n)! qslant C n! (n+1)! qslant C n! n+1 qslant C}\) czyli fałsz
a)2
b)12
2)Korzystamy z defincji notacji O mamy \(\displaystyle{ f(n)=O(g(n))}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego n\(\displaystyle{ |f(n)| qslant C |g(n)|}\)
a)\(\displaystyle{ 40^{n}=O(2^{n})}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego \(\displaystyle{ n}\) \(\displaystyle{ 40^{n} qslant C 2^{n} 20^{n} qslant C}\)czyli fałsz
b) \(\displaystyle{ (n+1)! qslant (2n)!}\) \(\displaystyle{ (2n)!=O(n!)}\) to istnieje dodatnia stała \(\displaystyle{ C}\), że dla dostatecznie dużego \(\displaystyle{ n}\) \(\displaystyle{ (2n)! qslant C n! (n+1)! qslant C n! n+1 qslant C}\) czyli fałsz