Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
70
1.Zbiory,ciągiifunkcje
Wpraktycenajbardziejpożądanyjestefektywnyczasdziałania
rzęduO(n)lubO(n·log2n).Wnastępnymprzykładzierozpatru-
jemydwaciągi,któreczęstospotykamyprzyszacowaniuczasu
działaniaalgorytmów.
PRZYKŁAD6
(a)Niechsn=1+1
2+...+1
ndlan≥1.Twierdzimy,że
sn=O(log2n).
Zauważmy,że
s2=1+
1
2
<2,
s4=s2+1
3
+
1
4)<2+(
1
2
+
1
2)=3,
s8=s4+(
1
5
+
1
6
+
1
7
+
8)<3+(
1
1
4
+
1
4
+
1
4
+
1
4)=4
itd.Ogólnies2k<k+1.(Rozumowanieindukcyjnez§4.2
przekonanasotymcałkowicie).Weźmyjakąśliczbęcałkowitą
n>2.Ograniczmyliczbęnkolejnymipotęgamidwójki,po-
wiedzmy2k<n≤2k+1.Ponieważk<log
2n,więcmamy
sn≤s2k+1<(k+1)+1<log2n+2.
Jeślin≥4,tolog2n≥2,awięc
sn<2log2ndlan≥4.
Stądsn=O(log2n).
(b)Jeślitn=n+n
2+n
3+...+n
ndlan≥1,totn=n·sn,
awięcnapodstawieprzykładu(a)tn<2n·log2ndlan≥4.
Zatemmamytn=O(n·log2n).
Następnetwierdzeniepodajekilkaogólnychfaktówdotyczą-
cychnotacjiO.Pamiętajmy,żenapisf(n)=O(g(n))poprostu
oznacza,żef(n)jestpewnymciągiem,któryjestO(g(n)).
Twierdzenie2
(a)Jeślif(n)=O(g(n))icjeststałą,toc·f(n)=O(g(n)).
(b)Jeślif(n)=O(g(n))ih(n)=O(g(n)),tof(n)+h(n)=
O(g(n)).
(c)Jeślif(n)=O(a(n))ig(n)=O(b(n)),tof(n)·g(n)=
O(a(n)·b(n)).
(d)Jeślia(n)=O(b(n))ib(n)=O(c(n)),toa(n)
=O(c(n)).
