Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
72
1.Zbiory,ciągiifunkcje
iskładnikiniższegorzędudladużychn.Zatemmoglibyśmyna-
pisać
6n4+20n2+1000=6n4+O(n2),
gdzieskładnikzawierającyOdotyczywyrażenia20n2+1000,
októrymwiemy,żespełniawarunek20n2+1000=O(n2).Takie
użycienotacjiOwwyrażeniachtypuf(n)+O(g(n))różnisię
niecoodsposobuużyciajejwrównościachf(n)=O(g(n)).Oba
sposobyjednaksązgodnezinterpretacją,żeO(g(n))oznacza
„ciąg,któregowyrazysąograniczoneprzezpewnąwielokrotność
g(n)dladostateczniedużychn”.Odtądbędziemyużywaćtej
notacjiwtakimznaczeniu.
Podobniejaknadaliśmysenswyrażenioma(n)+O(b(n)),
możemynapisaća(n)·O(b(n)),mającnamyśli„a(n)·f(n),gdzie
f(n)=O(b(n))”.Interpretująctowtakiwłaśniesposób,możemy
pisać„równości”takiejakwnastępnymtwierdzeniu.
Twierdzenie3
Dladowolnychciągówa(n)ib(n)mamy
(a)O(a(n))+O(b(n))=O(max{|a(n)|,|b(n)|}).
(b)O(a(n))·O(b(n))=O(a(n)·b(n)).
Tezdaniapoprostuoznaczają:jeślif(n)=O(a(n))oraz
g(n)=O(b(n)),tof(n)+g(n)=O(max{|a(n)|,|b(n)|})oraz
f(n)·g(n)=O(a(n)·b(n)).NaprzykładO(n3)+O(n4)=O(n4),
ponieważmax{n3,n4}=n4,aO(n3)·O(n4)=O(n7).Wprze-
ciwieństwiedoprawdziwychrówności,stwierdzeniateniewiele
znaczą,jeśliczytamyjeodprawejdolewej.
Dowódtwierdzenia3.(a)Niechf(n)=O(a(n))oraz
g(n)=O(b(n)).WtedyistniejąliczbydodatnieCiDtakie,że
|f(n)|≤C·|a(n)|oraz|g(n)|≤D·|b(n)|
dladostateczniedużychn.
Zatemmamy
|f(n)+g(n)|
≤|f(n)|+|g(n)|≤C·|a(n)|+D·|b(n)|
≤C·max{|a(n)|,|b(n)|}+D·max{|a(n)|,|b(n)|}
=(C+D)·max{|a(n)|,|b(n)|}
dladostateczniedużychn.Takwięcf(n)+g(n)=O(max{|a(n)|,
|b(n)|}).
Punkt(b)wynikanatychmiastztwierdzenia2(c).
