INF1130 Mathematiques pour informaticien

Chapitre 5

Comportement asymptotique des fonctions

Marie-Jean Meurs Automne 2015

5.1 Notation asymptotique 5.2 Croissance et combinaison

Notation asymptotique - definitionINF1130 ch5

Definition : Soient f et g des fonctions de R→ R ou de N→ R.On dit que :

f(x) est O(g(x)) s’il existe des constantes C > 0 et k telles que∀x > k, |f(x)| ≤ C|g(x)|

On dit alors que f ne croıt pas plus vite que g,ou que f a le meme comportement asymptotique que g.

Remarques :

� Pour demontrer que f(x) est O(g(x)), il suffit de trouver une pairede constantes C et k telles que l’on a ∀x ≥ k, |f(x)| ≤ C|g(x)| (*)

� S’il existe une paire C, k pour laquelle (*) est vraie, alors il existeune infinite de paires pour lesquelles (*) est vraie :

→ par exemple, toutes les paires C ′, k′ telles que C < C ′ et k < k′

rendent (*) vraie.1 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Notation asymptotique - exempleINF1130 ch5

Montrons que f definie sur N par f(n) = 3n2 − 2n + 3 est O(n2).

∀n ≥ 1, on a : f(n) ≤ 3n2 + 0 + 3n2

f(n) ≤ 6n2

D’ou en choisissant :

k = 1 et C = 6

on a bien : f est O(n2)

2 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Notation asymptotique - exempleINF1130 ch5

x

y

12

1 2 3

−1

0

1

2

3

Cf : y = x2

Cg : y = x2 − 1

Ch : y = 5x2 − 1

3 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Notation asymptotique - vocabulaire et proprietesINF1130 ch5

� O est appele symbole de Landau

� f(x) est O(g(x)) et g(x) est O(f(x)), on dit que :f et g sont du meme ordre (de complexite).

� En fait, O(g(x)) est un ensemble de fonctions contenant toutes lesfonctions d’ordre de complexite inferieur ou egal a celui de g.

� Si f(x) est O(g(x)), alors ∃C > 0, k, ∀x > k, |f(x)| ≤ C|g(x)|,d’ou si ∃l∈R, ∀x ≥ l, |g(x)| ≤ |h(x)|alors f(x) est O(h(x))

4 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Notation asymptotique - fonctions polynomesINF1130 ch5

Theoreme : Soit f definie sur R par :

f(x) = anxn + an−1x

n−1 + · · ·+ a1x + a0ou a0, a1, · · · an−1, an sont des constantes reelles.

Alors f(x) est O(xn)

� 3x4 + 2x3 + x− 5x + 1 est O(x4)

∀n ∈ N,� f(n) = 1 + 2 + 3 + · · ·+ n est O(n2)

� f(n) = n! = 1× 2× 3× · · · × n est O(nn)

� f(n) = logn! est O(n log n) (log en base 2)

� On a n < 2n d’ou log n < n et donc log n est O(n)

5 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Croissance et combinaison de fonctionsINF1130 ch5

Soient les fonctions f1, f2 et g1, g2.

Theoreme : Si f1(x) est O(g1(x)) et f2(x) est O(g2(x))alors

(f1 + f2)(x) est O(max(g1(x), g2(x)))

Corollaire : Si f1(x) est O(g(x)) et f2(x) est O(g(x))alors

(f1 + f2)(x) est O(g(x))

Theoreme : si f1(x) est O(g1(x)) et f2(x) est O(g2(x))alors

(f1f2)(x) est O(g1g2(x))

6 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

Croissances compareesINF1130 ch5

7 / 8

5.1 Notation asymptotique 5.2 Croissance et combinaison

ExercicesINF1130 ch5

Section Exercices

1.8 1, 2, 13, 15, 19, 20, 21

8 / 8