TD 1 Complexité Algorithmique

Université de la Manouba BUSINESS Année Universitaire
École Supérieure COMPUTING 2022-2023

d’Économie Numérique
Complexité
Semestre 1 Algorithmique Dr Mariem Abdouli
TD1
Exercice1:
1) Proposer trois algorithmes qui calculent la factorielle d'un entier naturel en utilisant
des structures itératives.
2) Calculer la complexité de chaque algorithme.
Corrigé:
1)
En utilisant la boucle En utilisant la boucle En utilisant la boucle

"Pour" "Tant que" "Répéter"
factorielle (n) factorielle (n) factorielle (n)
Debut Debut Debut
fact =1 fact = 1 fact = 1
pour i de 2 à n i=1 i=1
faire Tant que (i<=n) Répéter
fact = faire fact = fact *i
fact *i fact = fact *i i=i+1
fin pour i=i+1 jusqu'à i>n
factorielle = fact Fin tant que factorielle = fact
fin factorielle = fact fin
fin
2)
En utilisant la boucle En utilisant la boucle En utilisant la boucle

"Pour" "tant que" "répéter"
factorielle (n) factorielle (n) factorielle (n)
Debut Debut Debut
fact =1 fact = 1 fact = 1
pour i de 2 à n i=1 i=1
faire (n-1) Tant que (i<=n) Répéter
fact = faire (n) fact = fact *i
fact *i (1) fact = fact *i (1)
fin pour (1) i=i+1 (1)
factorielle = fact i=i+1 (1) jusqu'à i>n (n)
fin Fin tant que factorielle = fact
factorielle = fact fin
fin
C(n)=n-1 C(n) =2n C(n)=2n
1
Exercice 2:
1) Proposer deux algorithmes qui effectuent la permutation du contenue d'un tableau T
de taille 3.
2) Calculer la complexité temporelle et spatiale de chaque algorithme.
3) Comparer les complexités obtenues.
Corrigé:
1)
Avec une variable supplémentaire Avec trois variables supplémentaires
Permuter (T) Permuter (T)

Début Début
Entier Aux Entier Tancien[1],
Aux = T [1] Tancien[2], Tancien[3]
T [1]=T [2] Tancien[1]=T[1]
T [2]=T [3] Tancien[2]=T[2]
T [3]=Aux Tancien[3]=T[3]
T[1]= Tancien[2]
fin T[2]= Tancien[3]
T[3]= Tancien[1]
Fin
Ctemporelle(n)=4 Ctemporelle(n)=6
Cspatiale(n)=4*taille d'un entier Cspatiale(n)=6* taille d'un entier
3) Nous remarquons que le premier algorithme est plus efficace, car avec l'utilisation
d'une seule variable nous obtenons une complexité temporelle inférieure à celle lorsque
nous utilisons trois variables supplémentaires, de même pour la complexité spatiale.
Exercice 3:
Soit deux matrices M1 et M2 qui contiennent des éléments positifs.
M1: représenté par une matrice carrée de deux dimensions n.
M2: représenté par un tableau à une seule dimension.
1) Proposer un algorithme qui calcule la somme des éléments de M1
2) Proposer un algorithme qui calcule la somme des éléments de M2
3) Calculer la complexité de chaque algorithme.
2
Corrigé:
1) 2)
Somme (i, j, M) Somme (i, M)
Debut Debut
somme =0 somme =0
pour i de 1 à n faire (n) pour i de 1 à n faire (n)
pour j de 1 à n faire (n) somme = somme + M[i] (1)
somme=somme+M[i,j] (1) fin pour
fin pour fin
fin pour
fin
3)
La complexité de l'algorithme qui calcule la somme des éléments de M1 est: C(n)=n*n
La complexité de l'algorithme qui calcule la somme des éléments de M2 est: C(n)= n
Exercice 4:
1) Proposer un algorithme qui permet de trouver la case où le contenue est égale à une
valeur précisé en avance.
Avec T un tableau de longueur n, et la valeur à trouver est V
2) Calculer la complexité de votre algorithme lorsque la valeur est trouvée dans la

première case.
Exemple: n=6 et V=10
10 5 7 1 18 2
3) Calculer la complexité de votre algorithme dans le pire cas (C'est à dire lorsque la
variable n'existe pas dans le tableau)
Exemple: n=6 et V=10
9 5 7 1 18 2
Exercice5:
Soit f(n)=4n(n-1)
Montrer que f(n)=Θ (g(n)) en précisant g(n).
Corrigé:
3
Pour montrer que f(n) = Θ (g(n))
Il revient à monter que f(n) = O(g(n))
et f(n) = Ω(g(n))
Autrement: f(n) >= K1*g(n) (1)
f(n) <=K2*g(n) (2)
Pour n>K2=4
(1) f(n) =4n(n-1)= 4n2 -4n <= 4n2 = O(n2)
(2) f(n) =4n(n-1)= 4n2 -4n = 3n2 +n2 -4n >= n2 -4n = Ω (n2)
Donc f(n) = Θ(n2)
Exercice 6:
Calculer O et Ω pour les fonctions suivantes:
f(n)= 2ⁿ+5n+99
g(n)=8nlog(n) + n+12
Corrigé:
Selon l'hiérarchie des ordres de grandeurs:
f(n)= 2ⁿ+5n+99 = O(2ⁿ)
f(n)= 2ⁿ+5n+99 = Ω(n)
g(n) =8nlog(n) + n+12 = O (nlog(n))
g(n)=8nlog(n) + n+12 = Ω (n)
Execrice7:
Schématiser les 6 ordres de grandeurs dans la même courbe.
Exercice 8:
Soit f(n) et g(n) deux fonctions tel que:
f(n)= 7 n2 et g(n)= n3
Est ce que f(n)= O(g(n)) et g(n)=O(f(n))?
Corrigé: Avec le calcule de la limite de f(n) /g(n) lorsque n tend vers ∞.

TD 1 Complexité Algorithmique

Transféré par

Droits d'auteur :

Formats disponibles

TD 1 Complexité Algorithmique

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TD 1 Complexité Algorithmique

Transféré par

Droits d'auteur :

Formats disponibles

Université de la Manouba BUSINESS Année Universitaire

École Supérieure COMPUTING 2022-2023

2) Calculer la complexité de chaque algorithme.

En utilisant la boucle En utilisant la boucle En utilisant la boucle

En utilisant la boucle En utilisant la boucle En utilisant la boucle

2) Calculer la complexité temporelle et spatiale de chaque algorithme.

3) Comparer les complexités obtenues.

Avec une variable supplémentaire Avec trois variables supplémentaires

Permuter (T) Permuter (T)

M1: représenté par une matrice carrée de deux dimensions n.

M2: représenté par un tableau à une seule dimension.

1) Proposer un algorithme qui calcule la somme des éléments de M1

2) Proposer un algorithme qui calcule la somme des éléments de M2

3) Calculer la complexité de chaque algorithme.

La complexité de l'algorithme qui calcule la somme des éléments de M1 est: C(n)=n*n

La complexité de l'algorithme qui calcule la somme des éléments de M2 est: C(n)= n

Avec T un tableau de longueur n, et la valeur à trouver est V

2) Calculer la complexité de votre algorithme lorsque la valeur est trouvée dans la

Exemple: n=6 et V=10

Exemple: n=6 et V=10

Montrer que f(n)=Θ (g(n)) en précisant g(n).

Il revient à monter que f(n) = O(g(n))

Autrement: f(n) >= K1*g(n) (1)

f(n) <=K2*g(n) (2)

(1) f(n) =4n(n-1)= 4n2 -4n <= 4n2 = O(n2)

Donc f(n) = Θ(n2)

Selon l'hiérarchie des ordres de grandeurs:

f(n)= 2ⁿ+5n+99 = O(2ⁿ)

f(n)= 2ⁿ+5n+99 = Ω(n)

g(n) =8nlog(n) + n+12 = O (nlog(n))

g(n)=8nlog(n) + n+12 = Ω (n)

Est ce que f(n)= O(g(n)) et g(n)=O(f(n))?

Corrigé: Avec le calcule de la limite de f(n) /g(n) lorsque n tend vers ∞.

Vous aimerez peut-être aussi