Scribd
Importer
18 vues2 pages

Révision Complexité

Transféré par

rahma.azzabi
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
18 vues2 pages

Révision Complexité

Transféré par

rahma.azzabi
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

Université de la Manouba BUSINESS Année Universitaire

École Supérieure COMPUTING 2023-2024


d’Économie Numérique
Complexité
Semestre 1 Algorithmique Révision

Exercice1:

Remplir le tableau avec l’ordre de grandeur convenable selon les valeurs de « m » :

C(n,m) O(n2+m) O(n+m) O(n+2m) O(n+log(m))


m=O(1)
m=O(log(n))
m=O(n)
m=O(n2)

Exercice 2:

Selon la hiérarchie des ordres de grandeurs, calculer la complexité en grand O de ces


fonctions suivantes :

F(n)= 34n+log(2n)+100

F(n) = (8n + 67)log(n) + n2

F(n)= 3n+ √𝑛 + 71

F(n)= 24log(n)5 + 72n5

Exercice 3:

On considère les fonctions suivantes :

f1(n)= 34n+log(2n)+100 ; f2(n)= 24nlog(n)5 + 72n

f3(n)=∑ (𝑖 ∗ 𝑖) ; f4(n) = 1010 log(n) + √100

1) Pour chacune des fonctions, calculer sa complexité en grand O.


2) Selon leurs ordres de grandeurs, ordonner ces fonctions d’ordre plus faible
jusqu’à celle d’ordre le plus grand.

1
Exercice 4:

Calculer les sommes suivantes :

S1(n) = 4 * ∑ 𝑛

S2(n) = [l1=1 , u1=n , l2=i1 , u2=n] ; avec c(i1,i2)=i2 +1

S3(n) = [l1=1, u1=n , i2=1 , u2=n , l3=1 , u3=i2] ; avec c(i1, i2, i3) = 2

Exercice5:

Calculer la complexité de l’algorithme suivant :

Algorithme ex5
Var
i,j,x,a,l,u,n :entier
v :booléen
Début
Pour i de 1 à n faire
Recherche_dichotomique(v)
pour j de 1 à n faire
x←x+2
y←y*3x
pour k de 1 à n
z←z/5+4
finp
pour l de 1 à n faire
u←x+y
finp
finp
fin

Vous aimerez peut-être aussi