zadanie 1
Jaka jest najmniejsza naturalna wartość n, dla której algorytm o (dokładniej) złożoność \(\displaystyle{ 100n^2}\) działa (na tym samym komputerze) szybciej od algorytmu o dokładnej złożoności \(\displaystyle{ 2^n}\)?
zadanie 2
Przypuśćmy, że czas konieczny do wykonania algorytmu\(\displaystyle{ A}\) na pewnym komputerze dla danych o rozmiarze n wynosi t.
a) jaki jest czas potrzebny do wykonania tego algorytmu dla danych \(\displaystyle{ 16 \cdot n}\) na tym samym komputerze, jeśli złożoność czasowa tego algorytmu jest znana? Rozważ (dokładnie) złożoności: \(\displaystyle{ lg n}\), \(\displaystyle{ n}\) , \(\displaystyle{ n^2}\), \(\displaystyle{ 2^n}\) . Odpowiedź wyraź w języku zmiennej t.
b) Jaki jest maksymalny rozmiar danych dla tego algorytmu, jeśli dysponujemy czasem 256 razy większym? rozważ te same złożoności co w poprzednim podpunkcie Odpowiedź wyraź w języku zmiennej n.
koszt realizacji algorytmów
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
koszt realizacji algorytmów
Ad 1
Musisz po prostu znaleźć najmniejsze \(\displaystyle{ n}\), dla którego \(\displaystyle{ 100n^2 < 2^n}\). Najlepiej zrobić to z kalkulatorem w ręku, zdaje się, że wyjdzie \(\displaystyle{ 15}\), ale lepiej sprawdzić.
Ad 2 a)
Jedno dla przykładu:
Jeśli \(\displaystyle{ t= \lg n}\), to w sytuacji, gdy \(\displaystyle{ n' =16n}\), mamy:
\(\displaystyle{ t' = \lg n' = \lg (16n) = \lg 16 + \lg n = 4 + t}\)
czyli czas wzrośnie o cztery jednostki.
Ad 2 b)
Jedno dla przykładu:
Jeśli \(\displaystyle{ t= \lg n}\), czyli \(\displaystyle{ n=2^t}\) to w sytuacji, gdy \(\displaystyle{ t' =256t}\), mamy:
\(\displaystyle{ n' = 2^{t'} = 2^{256 t} = (2^t)^{256} = n^{256}}\)
czyli taki jest właśnie szukany rozmiar danych.
Pozostałe analogicznie.
Q.
Musisz po prostu znaleźć najmniejsze \(\displaystyle{ n}\), dla którego \(\displaystyle{ 100n^2 < 2^n}\). Najlepiej zrobić to z kalkulatorem w ręku, zdaje się, że wyjdzie \(\displaystyle{ 15}\), ale lepiej sprawdzić.
Ad 2 a)
Jedno dla przykładu:
Jeśli \(\displaystyle{ t= \lg n}\), to w sytuacji, gdy \(\displaystyle{ n' =16n}\), mamy:
\(\displaystyle{ t' = \lg n' = \lg (16n) = \lg 16 + \lg n = 4 + t}\)
czyli czas wzrośnie o cztery jednostki.
Ad 2 b)
Jedno dla przykładu:
Jeśli \(\displaystyle{ t= \lg n}\), czyli \(\displaystyle{ n=2^t}\) to w sytuacji, gdy \(\displaystyle{ t' =256t}\), mamy:
\(\displaystyle{ n' = 2^{t'} = 2^{256 t} = (2^t)^{256} = n^{256}}\)
czyli taki jest właśnie szukany rozmiar danych.
Pozostałe analogicznie.
Q.