Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
74
1.Zbiory,ciągiifunkcje
8.NiechAbędziepewnąstałądodatnią.Pokaż,żeAn<n!dladosta-
teczniedużychn.Wskazówka:przeanalizujprzykład3(b).
9.(a)Dlan∈Pniechsn=Σ
n
k=1
k2,więcsn=1+1
1
4+1
9+...+1
n2dla
n≥4.Pokaż,żesn=O(1).Wskazówka:pokaż,że1
k2≤(
k-1-1
1
k)
dlak≥2,awięc,żesn≤1+Σ
n
k=2(
k-1-1
1
k)=2-
n.
1
(b)Pokaż,żetn=O(n
2),jeślitn=Σ
n
k=1k=1+2+...+n.
10.(a)Pokaż,żejeślisn=Σ
n
k=1k2,tosn=O(n3).
(b)NiechmbędzieustalonąliczbązezbioruP.Definiujemytn
=Σ
n
k=1km.Pokaż,żetn=O(nm+1).
11.Pokaż,żejeślif(n)=3n
4+O(n)ig(n)=2n3+O(n),to:
(a)f(n)+g(n)=3n
4+O(n3),(b)f(n)·g(n)=6n7+O(n5).
12.Pokaż,że
(a)(5n3+O(n2))·(3n4+O(n3))=15n7+O(n6),
(b)(5n3+O(n))·(3n4+O(n2))=15n7+O(n5).
13.Wyjaśnij,dlaczegoprawdziwesąwłasności(a)i(c)wtwierdzeniu2.
14.(a)Udowodnijbezpośrednioztwierdzenia2,żejeślia(n)=O(c(n))
ib(n)=O(c(n)),toO(a(n))+O(b(n))=O(c(n)).
(b)Zauważ,żetodajeinnydowódtwierdzenia3(a).
15.Toćwiczeniepokazuje,żetrzebabyćostrożnym,używającdzielenia
wobliczeniachwykorzystującychnotacjęO.
(a)Niecha(n)=n
5ib(n)=n.Zauważ,żea(n)=O(n5),natomiast
b(n)=O(n
2),alea(n)/b(n)niejestO(n3).
(b)Podajprzykładyciągówa(n)ib(n)takich,żea(n)=O(n
6)
ib(n)=O(n
2),alea(n)/b(n)niejestO(n4).
16.Pokaż,żelog
10n=O(log
2n).
17.Dlakażdejliczbynaturalnejn∈Pniechcyfr(n)oznaczaliczbęcyfr
wrozwinięciudziesiętnymliczbyn.
(a)Pokaż,że10
CYFR(n)-1≤n<10CYFR(n).
(b)Pokaż,żelog
10njestO(cyfr(n)).
(c)Pokaż,żecyfr(n)jestO(log10n).
(d)Niechcyfr2(n)będzieliczbącyfrwrozwinięciudwójkowymliczby
n.JakijestzwiązekmiędzyO(cyfr(n))iO(cyfr2(n))?
To,cojestnajważniejszewtymrozdziale
Abysprawdzić,czydobrzerozumiesztreśćtegorozdziału:
1.Przekonajsię,żepotrafiszzdefiniowaćkażdepojęcieiozna-
czenieorazmożeszopisaćkażdąmetodę.
