AIDE-MÉMOIRE
logb (x) 1
loga (x) = loga (b) logb (x) loga (x) = logb (a) = ax = bx logb (a)
logb (a) loga (b)
y
loga 1 = 0 loga a = 1 loga x = y loga x
loga xy = loga x + loga y
x jxk lxm
loga = loga x − loga y x ≤ dxe < x + 1 x − 1 < bxc ≤ x x= +
y 2 2
jmk
m mod n = m − n
n
√ n
n! ≈ 2πn ne lorsque n → ∞, dloga (n + 1)e = bloga nc + 1 pour n entier
d 1 d d f (x) d
loga (f (x)) = loga (e) × × f (x) ; a = af (x) × ln a × f (x) ;
dx f (x) dx dx dx
Z c+1
d d x
(f (x))c = c × (f (x))c−1 × f (x) ; xc dx = .
dx dx c+1
Z Z Z Z
1
u dv = uv − v du ; dx = ln |x| + C ; ln x dx = x ln x − x + C ;
x
Z u u
X Z u+1
f (x)dx ≤ f (i) ≤ f (x)dx pour f (x) nulle part décroissante
l−1 i=l l
Z u+1 u
X Z u
f (x)dx ≤ f (i) ≤ f (x)dx pour f (x) nulle part croissante
l i=l l−1
La règle de L’Hospital
Soit f et g deux fonctions telles que lim f (n) = ∞ et limn→+∞ g(n) = ∞ (ou lim f (n) = 0 et
n→+∞ n→+∞
limn→+∞ g(n) = 0). Alors
f (n) f 0 (n)
lim = lim 0
n→+∞ g(n) n→+∞ g (n)
pourvu que cette dernière limite existe.
La notation asymptotique
def
Ω(g(n)) = {t(n) | ∃c1 > 0, ∃n0 ∈ N ∀n ≥ n0 : c1 · g(n) ≤ t(n)}
def
O(g(n)) = {t(n) | ∃c2 > 0, ∃n0 ∈ N ∀n ≥ n0 : t(n) ≤ c2 · g(n)}
def
Θ(g(n)) = {t(n) | ∃c1 , c2 > 0, ∃n0 ∈ N ∀n ≥ n0 : c1 · g(n) ≤ t(n) ≤ c2 · g(n)}
Utilisation des limites pour comparaison d’ordre
c (fini) > 0 alors f (n) ∈ Θ(g(n))
f (n)
si lim = 0 alors f (n) ∈ O(g(n)) et f (n) 6∈ Θ(g(n))
n→+∞ g(n)
+∞ alors f (n) ∈ Ω(g(n)) et f (n) 6∈ Θ(g(n))
Les règles du maximum
t1 (n) ∈ Ω (g1 (n)) ∧ t2 (n) ∈ Ω (g2 (n)) ⇒ t1 (n) + t2 (n) ∈ Ω (max{g1 (n), g2 (n)})
t1 (n) ∈ O (g1 (n)) ∧ t2 (n) ∈ O (g2 (n)) ⇒ t1 (n) + t2 (n) ∈ O(max{g1 (n), g2 (n)})
t1 (n) ∈ Θ (g1 (n)) ∧ t2 (n) ∈ Θ (g2 (n)) ⇒ t1 (n) + t2 (n) ∈ Θ(max{g1 (n), g2 (n)})
Sommations
b n n
X X n(n + 1) X 1
c = (b − a + 1) × c ; i= ; i2 = n(n + 1)(2n + 1) ;
i=a i=1
2 i=0
6
n n+1 n n n
X a −1 X X X
ai = ; i2i = (n − 1)2n+1 + 2 ; f (n − i) = f (i) ;
i=0
a−1 i=1 i=0 i=0
Règle de l’harmonie
— Une fonction f (n) est éventuellement non décroissante s’il existe un n0 où f (n) est non décrois-
sante sur l’intervalle [n0 , ∞) ;
— Une fonction éventuellement non décroissante f (n) est harmonieuse si f (2n) ∈ Θ(f (n)) ;
— Si C(n) est éventuellement non décroissante, si f (n) est harmonieuse et si C(n) ∈ Θ(f (n)) pour
n = bk avec k ∈ N alors C(n) ∈ Θ(f (n)) ∀n ∈ N.
Théorème général
Si T (n) est une récurrence donnée par T (n) = rT (n/b) + f (n) pour les n de la forme bk avec f (n) ∈
Θ(nd ), alors
r < bd ⇒ T (n) ∈ Θ(nd ) ∀n ∈ N
r = bd d
⇒ T (n) ∈ Θ(n log n) ∀n ∈ N
r > bd ⇒ T (n) ∈ Θ(nlogb r ) ∀n ∈ N
Pr n
Le théorème général s’applique aussi pour les récurrences de la forme T (n) = i=1 T b
+ ci + f (n)
pour les n de la forme bk avec f (n) ∈ Θ(nd ).
Théorème sur les récurrences linéaires homogènes d’ordre 2
Soit han in∈N une suite définie récursivement par :
a0 = a
a1 = b
an = r · an−1 + s · an−2 ∀n : N − {0, 1}
où a, b, r et s sont des constantes réelles.
Soit p, le polynôme caractéristique de han in∈N , (c.-à-d. : p(x) = x2 − rx − s).
Et soit ρ1 et ρ2 les zéros de ce polynôme.
Alors,
4 = A · (ρ1 )n + B · (ρ2 )n ∀n : N si ρ1 6= ρ2 .
an
* = A · (ρ1 )n + B · n · (ρ1 )n ∀n : N si ρ1 = ρ2
Où A et B sont deux constantes déterminées par les conditions initiales de la récurrence (c.-à-d. : par
a0 = a et a1 = b).
