Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
24
1.Podstawowezasadyanalizyalgorytmów
Pz
n
()
=
∑
k
≥
0
Pz
nk
k
Zauważmy,żewówczas
∑
k
≥
0
P
nk
=
1
WartośćoczekiwanąiwariancjęzmiennejlosowejX
nmożnawyrazićzapomocąwartości
pochodnychfunkcjiP
n(z)dlaz=1wnastępującysposób:
aveX
(
n
)
=′
P
n
()
1
var
(
X
n
)
=′′
P
n
()
1
+′
P
n
()
1
−′
P
n
()
1
2
ponieważ
Pz
n
′
()
=
∑
k
≥
1
kpz
nk
k
−
1
i
Pz
n
′′
()
=
∑
k
≥
2
kk
(
−
1
)
pz
nk
k
−
2
Stąd
P
n
′
()
1
=
∑
kp
nk
i
P
n
′′
()
1
=
∑
kk
(
−
1
)
p
nk
,azatem
k
≥
1
k
≥
2
varX
(
n
)
=
∑
(
k
−′
P
n
()
1
)
2
p
nk
=
∑
kp
2
nk
−
2
P
n
′
()
1
∑
kp
nk
+′
P
n
()
1
2
∑
p
n
k
=
k
≥
0
k
≥
0
k
≥
0
k
≥
0
=
∑
kk
(
−
1
)
p
nk
+
∑
kp
nk
−
2
P
n
′
()
1
2
+′
P
n
()
1
2
=′′
P
n
(
1
)
+′
P
n
()
1
−′
P
n
()
1
2
k
≥
0
k
≥
0
Możnawięcwyznaczyćwielkościave(X
n)ivar(X
n)(acozatymidzierównieżzłożoność
oczekiwanąioczekiwanąwrażliwośćalgorytmu),nieznającexplicitérozkładup
nk,atylko
jegofunkcjętworzącą.
1.4.
Poprawnośćsemantyczna
Poprawnośćsemantycznaoznacza,żeprogramwykonujepostawioneprzednimzada-
nie.Stosowanąmetodądowodujestindukcjamatematycznawzględemliczbypowtórzeń
instrukcjiiteracyjnejbądźpoziomuzagnieżdżeniarealizacjiproceduryrekurencyjnej.Roz-
ważmynaprzykładalgorytmpotęgowaniabinarnego:
