Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
§1.6.NotacjaO
73
PRZYKŁAD7
(a)Ponieważn2+13n=O(n2)oraz(n+1)3=O(n3)
(przemyślto),więcnapodstawietwierdzenia3(a)mamy
(n2+13n)+(n+1)3=O(n3)oraznapodstawietwierdzenia
3(b)mamy(n2+13n)(n+1)3=O(n5).
(b)Jeślia(n)=O(n4)ib(n)=O(log
2n),toa(n)·b(n)
=O(n4·log
2n),a(n)2=O(n8)orazb(n)2=O(log2
2n).Za-
uważmy,żelog
2
2noznacza(log2n)
2.
(c)Wnioskiemzprzykładu5(e)jestteżrówność
m
Σ
akn
k=amnm+O(nm-1),
jeśliam/=0.
k=o
ĆWICZENIADO§1.6
1.Dlakażdegozponiższychciągówznajdźnajmniejsząliczbęktaką,że
f(n)=O(n
(a)f(n)=13n
(c)f(n)=(n
k).
3+3n-1)4
2+4n-73
(b)f(n)=(n
2+1)(2n4+3n-8)
(d)√n+1
2.Powtórzćwiczenie1dlaciągów:
(a)f(n)=(n
(c)f(n)=√n2+n,
2-1)7,
(b)f(n)=√n2-1,
(d)f(n)=(n
2+n+1)2·(n3+5).
3.Dlakażdegozponiższychciągówpodajciąga(n)zhierarchiiwtwier-
dzeniu1taki,żef(n)=O(a(n))oraza(n)znajdujesięmożliwienaj-
bardziejnalewowtejhierarchii.
(a)f(n)=3
n
(b)f(n)=n
3·log
2n
(c)f(n)=log2n
4.Powtórzćwiczenie3dlaciągów:
(a)f(n)=n+3·log2n,
(b)f(n)=(n·log2n+1)
2,
(c)f(n)=(n+1)!.
5.Sprawdź,czykażdazponiższychrównościjestprawdziwaczyfałszywa.
Wkażdymzprzypadkówuzasadnijswojąodpowiedź.
(a)2n+1=O(2n)
(b)(n+1)
(d)(200n)
2=O(n2)
2=O(n2)
(c)22n=O(2n)
6.Powtórzćwiczenie5dlaciągów:
(a)log73
(c)log
2nn=O(log
2n=O(√n),
2n),
(b)log
(d)(√n+1)
2n73=O(log
4=O(n2).
2n),
7.Czyponiższezdaniasąprawdziweczyfałszywe?Uzasadnijodpowiedź.
(a)40n=O(2n)
(b)(40n)
(d)(n+1)
2=O(n2)
40=O(n40)
(c)(2n)!=O(n!)
