Scribd
Importer
270 vues7 pages

Notation asymptotique et propriétés

Ce document explique la notation asymptotique grand O qui donne une borne supérieure du taux de croissance d'une fonction. Il présente également les propriétés de grand O, les logarithmes, les exposants, ainsi que les notations grand Ω et grand Θ.

Transféré par

Moustapha Djibrilla
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
270 vues7 pages

Notation asymptotique et propriétés

Ce document explique la notation asymptotique grand O qui donne une borne supérieure du taux de croissance d'une fonction. Il présente également les propriétés de grand O, les logarithmes, les exposants, ainsi que les notations grand Ω et grand Θ.

Transféré par

Moustapha Djibrilla
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Notation asymptotique

Notation Grand O
Étant donné des fonctions f (n) et g(n), on dit que

f (n) est O(g(n))
s’il existe des constantes c > 0 et n0 1 telles que

f (n) cg(n) ⇥n, n n0
d’exécution

cg(n)
Temps

f(n)

n0 Taille de l’entrée

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 1
Grand O et taux de croissance
La notation grand O donne une borne supérieure du taux de
croissance d’une fonction.

La phrase “f(n) est O(g(n))” signifie donc que le taux de


croissance de f(n) est plus petit ou égal au taux de croissance
de g(n).

On peut utiliser la notation O pour ordonner les fonctions à


partir de leur taux de croissance.
2 n n
1  logn  n  nlogn  n  2  n

La notation grand O est réflexive et transitive.

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 2
Propriétés de O
1) Règle du seuil: Si f et t sont 2 fonctions strictement positives de!
N ! R+, alors
t(n) 2 O(f (n)) () 9c0 2 R+ tel que 8n 2 N, t(n)  c0 f (n)

2) Règle du maximum: Soient f et t deux fonctions de N ! R+, alors


O(f (n) + t(n)) = O(max(f (n), t(n)))

3) Si f (n) 2 O(h1 (n)) et g(n) 2 O(h2 (n)), alors (f · g)(n) 2 O(h1 · h2 (n))

4) O(f (n)) = O(g(n)) () f (n) 2 O(g(n)) et g(n) 2 O(f (n))

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 3
Rappel: logarithmes et exposants

Propriétés des logarithmes


log b (xy) = log b (x) + log b (y)
log b (x/y) = log b(x) - log b (y)
a
logb ( x ) = a log b (x)

Propriétés des exposants


(b+c) b c
a =a a
bc b c
a = (a )
c b-c
ab / a = a

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 4
Grand Ω et grand Θ
Grand Ω
Étant donné des fonctions f(n) et g(n), on dit que
f(n) est Ω(g(n))
s’il existe des constantes c > 0 et n0 1 telles que
f(n) cg(n) 8entier n n0

Grand Θ
Étant donné des fonctions f(n) et g(n), on dit que
f(n) est Θ (g(n))
si f(n) est O(g(n)) et f(n) est Ω (g(n)), i.e s’il existe
des constantes c 1 > 0, c2 > 0 et n0 1 tels que
c 1 g(n)  f(n)  c2 g(n) 8 n n0

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 5
Intuition: notation asymptotique

Grand O
f(n) est O(g(n)) si f(n) est asymptotiquement plus
petite ou égale à g(n)

Grand Ω

f(n) est Ω (g(n)) si f(n) est asymptotiquement plus


grande ou égale à g(n)

Grand Θ
f(n) est Θ(g(n)) si f(n) est asymptotiquement égale à
g(n)

IFT2125, Sylvie Hamel


Université de Montréal
Notation asymptotique 6

Vous aimerez peut-être aussi