Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
§1.6.NotacjaO
67
Nierównośćtazachodzinawetwtedy,gdynniejestliczbącałko-
witą,awięcmożemyzastąpićliczbęnliczbąm
√n,abyotrzymać
log2(m
√n)m<m
√ndlam
√n≥4m2,tzn.
log2n<m
√n
dlan≥(4m2)m.
Zatemlog2n<m
√ndladostateczniedużychn.
Zgrubszamówiąc,przykład2(b)pokazuje,że2nrośnieszyb-
ciejniżjakakolwiekpotęgan,aprzykład2(c)mówinam,żelog2n
rośniedużowolniejniżjakikolwiekpierwiastekzn.Zanimwyra-
zimytespostrzeżeniawsposóbbardziejprecyzyjny,popatrzmy
nakilkanastępnychnierówności.
PRZYKŁAD3
(a)Mamy
2n<n!<nn
dla
n≥4.
Dlan=4nierównościtesąoczywiste:16<24<256.Dlan>4
mamyn!=(4!)·5·6·...·(n−1)·n.Pierwszyczynnik4!jest
większyod24,akażdyzpozostałychn−4czynnikówjestwiększy
od2.Zatemn!>24·2n-4=2n.
Nierównośćn!<nnjestoczywista,ponieważn!jestiloczy-
nemliczbnaturalnych,zktórychwszystkiepozajednąsąmniej-
szeodn.
(b)Nieograniczajmysiędoliczby2ipokażmy,że40n<n!
dladostateczniedużychn.Dowódbędziebardziejpomysłowyniż
dowódnierówności2n<n!.Zauważmy,żedlan>80możemy
napisać
n!>n(n−1)·...·81
(n−80czynników)
>80·80·...·80
(n−80czynników)
=80n-8o=40n·(2n·1
8o80)>40n
przyzałożeniu,że2n>808olubn>log
2(808o)=80·log
280
≈505,8.Byłoto„grube”szacowanie,wtymsensie,żepominęli-
śmydużyczynnik(taknaprawdę80!),piszącn!>n(n−1)·...·81.
Gdybyśmypotrzebowalibliższejinformacjiotym,gdzien!staje
sięwiększeod40n,moglibyśmydokonaćstaranniejszegooszaco-
wania.To,cozrobiliśmy,byłojednakwystarczającedopokazania,
że40n<n!dladostateczniedużychn.
Abywyrazićdokładniej,comamynamyślimówiąc„...rośnie
jak...dladużychn”,musimywprowadzićnoweoznaczenie,na-
zywanenotacjąO.Głównymzastosowaniemtejnotacjibędzie
opisanieczasudziałaniaalgorytmów.
