[ Pobierz całość w formacie PDF ]
.Z drugiej jednak strony oszacowanie asymptotyczne wystarczy do naszych celów ijest łatwiejsze do uzyskania.Przykład 1.22 Rozważmy trzy algorytmy: pierwszy działający w czasie ,drugi w czasie i trzeci w czasie.Funkcje te określają czasdziałania na pewnym konkretnym komputerze.Niech , i oznazczają długościwejść, dla których algorytmy dają odpowiedz w ciągu jednej sekundy, to znaczyPrzypuśćmy teraz, że mamy 1000 razy szybszy komputer i pytamy jakie wejścia terazmogą być policzone przez te algorytmy w ciągu jednej sekundy.Dla pierwszego algorytmu działającego w czasie liniowym możemy teraz obliczać1000 razy dłuższe dane wejściowe, ponieważ.Dla drugie-go algorytmu działającego w czasie sześciennym możemy teraz obliczać 10 razy dłuższedane wejściowe, ponieważ.Dla trzeciego algorytmu działają-cego w czasie wykładniczym możemy teraz obliczać tylko dane wejściowe o 10 dłuższe,ponieważ.1.11 Zadania1.Oblicz dla.2.Oblicz.3.Oblicz.4.Niech , i.Oblicz ,, , , ,.5.Niech bedzie zbiorem indeksów.Dla każdego określamy�zbór.Oblicz , , oraz. 1.11.Zadania 156.Niech ,.Wypisz elementy oraz,7.Niech bedzie zbiorem indeksów.Dla każdego określamy�zbór oraz dzieli.Oblicz oraz.8.Uporządkuj następujący zbiór słów [Fragment wiersza Ptasie radio Juliana Tu-wima] według porządku leksykograficznego i kanonicznego: słowik, wróbel, kos,jaskółka, kogut, dzięcioł, gil, kukułka, szczygieł, sowa, kruk, czubatka, drozd, siko-ra i dzierlatka, kaczka, gąska, jemiołuszka, dudek, trznadel, pośmieciuszka, wilga,zięba, bocian, szpak.9.Udowodnij wzór (1.1) na sumę ciągu arytmetycznego.10.Udowodnij wzór (1.2) na sumę ciągu geometrycznego.11.Udowodnij wzór (1.3).12.Udowodnij wzór (1.4).13.Udowodnij lemat 1.19,14.Udowodnij zależności z przykładów 1.16, 1.17, 1.18,
[ Pobierz całość w formacie PDF ]
