Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
64
1.Zbiory,ciągiifunkcje
(c)wek(n)=(an,bn)dlan∈N.
12.Znajdźwyrazyciągówlog
2noraz√ndlan=16,64,256,4096ipo-
równajje.
13.(a)Używająckalkulatoralubinnegourządzenia,uzupełnijtablicę1.6.
(NapiszE,jeśliwynikwykraczapozamożliwościkalkulatora.)
(b)Omówzauważonewzględneszybkościwzrostuciągówn4,4n,n20,
20nin!.
Tablica1.6
10
25
50
n
5
3,91·105
n4
1,27·1030
4n
9,54·1013
n20
1,02·1013
3,2·106
20n
3,63·106
n!
14.Powtórzćwiczenie13dlatablicy1.7.
100
104
106
50
n
log10n
1,70
7,07
Tablica1.7
√n
20·4
53,18
√n
√n·log10n
4
4,52
15.Zwróćuwagęnawykładnikipotęgwystępującewkolumnie2nwta-
blicy1.5.Zauważteż,żelog
102≈0,30103.Jaktowytłumaczyć?
§1.6.NotacjaO
Winformatyceciągipojawiająsięwnaturalnysposóbjakoli-
stykolejnowyliczanychwartości;ciągisilniaidwazprzykładu
2w§1.5sąciągamitegorodzaju.Inneważnezastosowanie,szcze-
gólniegdyanalizujemyalgorytmy,znajdująciągiwzagadnieniu
szacowaniaczasuwykonywaniaobliczeńdlaokreślonychdanych
wejściowych.
Zastanówmysię,naprzykład,nadposortowaniemwkolej-
nościrosnącejlistyndanychliczbcałkowitych.Jestwielealgo-
rytmów,którewykonujątozadanie;możemyprawdopodobnie
samodzielniewymyślićkilkaróżnychsposobów.Niektórealgo-
rytmysąszybszeniżinneiwszystkieznichwymagająwięcej
czasu,gdynstajesięwiększe.Jeślinjestmałe,prawdopodobnie
niemaróżnicy,którąmetodęwybierzemy,aledladużychnwła-
ściwywybórmetodymożeprowadzićdoistotnegozaoszczędzenia
