Notatki do wykªadu
Mateusz Kwa±nicki
11 Asymptotyka
Cz¦sto interesuj¡ca jest nie tyle granica ci¡gu (an), ale szybko±¢ wzrostu an wraz z n. W ªatwy sposób mo»na to za pomoc¡ tzw. notacji asymptotycznej.
Denicja. Niech (cn) b¦dzie dowolnym ci¡giem liczb dodatnich. Okre±lamy:
|a
O(c
n|
n) =
(an) : lim sup
< ∞
,
n→∞
cn
|a
Ω(c
n|
n) =
(an) : lim inf
> 0
,
n→∞
cn
|a
o(c
n|
n) =
(an) : lim sup
= 0
,
n→∞
cn
a
a
Θ(c
n
n
n) =
(an) : lim sup
< ∞, lim inf
> 0
= O(cn) ∩ Ω(cn).
n→∞
cn
n→∞
cn
Cz¦sto zamiast (an) ∈ O(cn) piszemy an = O(cn) itp.
Twierdzenie. Zaªó»my, »e wyrazy ci¡gów (an) i (bn) s¡ dodatnie. Wówczas: an = o(bn) =⇒ an = O(bn), an = Ω(bn) ⇐⇒ bn = O(an), an = O(bn) ⇐⇒ O(an) ⊆ O(bn), 1
1
an = O(bn) ⇐⇒
= O
,
bn
bn
1
1
an = o(bn) ⇐⇒
= o
,
bn
bn
an = Θ(bn) ⇐⇒ an = O(bn) oraz an = Ω(bn), an = Θ(bn) ⇐⇒ bn = Θ(an), an = Θ(bn) ⇐⇒ Θ(an) = Θ(bn), an = Θ(bn) ⇐⇒ an = O(bn) oraz bn = O(an).
Twierdzenie. Zachodzi: an = O(cn) oraz bn = O(dn) =⇒ an ± bn = O(cn + dn) oraz an · bn = O(cn · dn).
Ponadto O(K · cn) = O(cn). Analogiczne wªasno±ci maj¡ pozostaªe klasy.
Twierdzenie. Zachodz¡ nast¦puj¡ce zawierania:
• je±li K < K0, to O(nK) ⊆ O(nK0);
• je±li 0 < L < L0, to O(Ln) ⊆ O((L0)n);
• je±li L > 1, to O(nK) ⊆ O(Ln);
• je±li 0 < L < 1, to O(Ln) ⊆ O(nK); 1
• je±li K > 0, to O((ln n)M ) ⊆ O(nK);
• je±li K < 0, to O(nK) ⊆ O((ln n)M ).
Twierdzenie. Zachodzi: n
X 1
Hn =
= Θ(ln n),
j
j=1
za± dla K 6= −1,
n
X jK = Θ(nK+1).
j=1
Twierdzenie. Zachodzi:
!
nn
nn+ 12
n! = Ω
,
n! = Θ
.
en
en
12 Wa»ne granice, szeregi i funkcje Szereg harmoniczny:
∞
X 1 = ∞,
n
n=1
oraz szereg anharmoniczny:
∞
X (−1)n−1 = ln(2).
n
n=1
Szereg geometryczny:
∞
X
1
xn =
,
|x| < 1.
1 − x
n=0
Funkcja wykªadnicza:
∞
X xn
x n
exp(x) =
= lim
1 +
,
x ∈ R.
n!
n→∞
n
n=0
Funkcja dzeta Riemanna:
∞
X
1
ζ(s) =
,
s > 1;
ns
n=1
π2
π4
ζ(2) =
, ζ(4) =
, ...
6
80
Wzór Stirlinga:
√
∞
!
nn
X (−1)k B
1
n! =
2πn
exp
1 +
k ·
,
(Bn) ci¡g liczb Bernoulliego.
en
k(k − 1)
nk−1
k=2
Wzór Wallisa:
((2n)!!)2
π = lim
,
0!! = 1!! = 1, k!! = k · (k − 2)!!; n→∞ (2n + 1)!!(2n − 1)!!
24n(n!)4
π = lim
.
n→∞ (2n + 1)!(2n − 1)!
2