Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
§1.6.NotacjaO
69
Twierdzenie1
Otohierarchiapewnychznanychciągówuporządkowanych
wtensposób,żekażdyznichjestOodwszystkichciągówna
prawoodniego:
1,log2n,...,4
√n,3
√n,√n,n,n·log2n,n√n,n
2,n3,n4,...,
2n,n!,nn.
Ciągstały1wpowyższymtwierdzeniujestokreślonywzorem
1(n)=1dlawszystkichn.Onwogólenierośnie.
PRZYKŁAD5
(a)Przypuśćmy,żeg(n)=ndlawszystkichn∈N.Stwierdze-
nief(n)=O(n)oznacza,że|f(n)|jestograniczonyzgóryprzez
pewnąstałąwielokrotnośćn,tzn.żeistniejetakaliczbaC>0,
że|f(n)|≤Cndlaodpowiedniodużychn∈N.
(b)Przypuśćmy,żeg(n)=1dlawszystkichn∈N.Mówimy,
żef(n)jestO(1),jeśliistniejetakastałaC,że|f(n)|≤Cdla
wszystkichdużychn,tzn.żewtedywartości|f(n)|sąograniczone
zgóryprzezpewnąstałą.
(c)Ciągsokreślonywzoremsn=3n2+15nspełniawaru-
neksn=O(n2),ponieważn≤n2dlan≥1,azatemmamy
|sn|≤3n2+15n2=18n2dlawszystkichdostateczniedużychn.
(d)Ciągtdanywzoremtn=3n2+(−1)n·15nrównieżspełnia
warunektn=O(n2).Awięc,takjakwprzykładzie(c),mamy
|tn|≤3n2+15n2≤18n2dlan≥1.
(e)
Możemy
uogólnić
przykłady
(c)
oraz
(d).
Jeśli
f(n)=amnm+am-1nm-1+...+ao,gdzieam/=0,jest
wielomianemstopniamzmiennejn,to|aknk|≤|ak|·nmdla
k=0,1,...,m−1,więc
|f(n)|≤|amn
m|+|am-1nm-1|+...+|ao|
≤(|am|+|am-1|+...+|ao|)·n
m,
azatemf(n)=O(nm).Pierwszanierównośćzachodzidlatego,
że
|x1+x2+...+xi|≤|x1|+|x2|+...+|xi|
dladowolnegoskończonegociągux1,x2,...,xizezbioruR.
Zewzględunaprzykład5(e),mówimy,żeciągf(n)rośnie
wielomianowo,jeślif(n)=O(nm)dlajakiejśdodatniejliczby
całkowitejm.Zteoretycznegopunktuwidzenia,algorytmy,któ-
rychczaswykonywaniarośniewielomianowo,sąuważanezaprak-
tyczne.Oczywiście,żesąonepraktyczne,jeślisięporównajena
przykładzalgorytmami,którychczasdziałaniajestrzęduO(2n).
