Série N°2 Complexité : correction
Exercice 1
Soit un graphe G=(X , U) où n=∣X∣ et m=∣u∣ . Soit A la matrice d'adjacence de G. A est une
matrice carrée d'ordre n tel que a(i , j)=1 s'il existe un arc entre les noeuds i et j, 0 sinon. On
désire calculer le maximum des degrès des n noeuds.
Ecrire l'algorithme correspondant. Est il de coût minimal?
Indications :
Pour chaque noeud, on calcule ne nombre d'arc incident. Ensuite on cherche le noeud avant le plus
grand nombre.
T:tableau [1:n]
//phase de calcul
Pour i de 1 à n faire
t[i]=0
Pour j de 1 à n faire
t[i]+=t[j]
fin pour
fin pour
//phase du recherche du maximum
Max=1
Pour i de 2 à n faire
si t[i]>max alors max=t[i]
fin si
Fin pour
La complexité de cet algorithme est O(n2 )
Exercice 2
Normaliser la boucle suivante :
Pour i de n à m pas -p
corps(i)
Fin pour
avec n>m et p>0
Indications :
Phase 1: Rendre le pas positif
on pose j=n+m-i
Pour m à n pas p faire
corps (n+m-j)
Fin pour
Phase 2 : rendre le pas = 1
n−m
on pose q=[ ]
p
Pour k=0 à q faire
corps(n-kp)
Fin pour
Exercice 3
Ecrire l'algorithme récursif qui permet de chercher un élément v dans un tableau T et évaluer sa
complexité.
Indications:
D'abord, on suppose que le tableau T est trié
Recheche (T,d, f, v)
Si d==f
alors revoyer v==t[d]
fin si
tantque d>f
m=(d+f)/2
si t[m]>x alors recherche (T,d,m,v)
sinon recherche (T,m+1,f,v)
fin si
Fin pour
La complexité de cette procedure est O(log 2 (n)) : en effet, on a au plus log2 (n) appels à faire
avant d'arriver à d=f
Exercice 4
Rappeler l'algorithme de tri rapide. Evaluer sa complexité (en illustrant les details du calcul).
Algorithme TRI RAPIDE
partitionner(tableau T, premier, dernier, pivot)
échanger T[pivot] et T[dernier]
j := premier
pour i de premier à dernier - 1
si T[i] <= T[dernier] alors
échanger T[i] et T[j]
j := j + 1
échanger T[dernier] et T[j]
renvoyer j
tri_rapide(tableau t, entier premier, entier dernier)
début
si premier < dernier alors
pivot := choix_pivot(t,premier,dernier)
pivot := partitionner(t,premier, dernier,pivot)
tri_rapide(t,premier,pivot-1)
tri_rapide(t,pivot+1,dernier)
fin si
fin
La complexité de l'algorithme dépend du choix du pivot
En moyenne : O(nlog 2 (n))
Au pire des cas : O(n2 )
La complexité provient du fait que cette recurrence est de type T(n)=cn+2T(n/2).
Exercice 5
La suite de Fibonacci est définie comme suit
{ }
1 si n = 0
f (n)= 1 si n = 1
f(n-1) + f(n-2) si n >= 2
1. Écrire la version itérative de la fonction de Fibonacci. Évaluer sa complexité
2. Écrire la version récursive de cette même fonction. Évaluer sa complexité
Indications :
1.
u=1
v=1
Pour i de 2 à n faire
s=u+v
u=v
v=s
fin Pour
La complexité est O(n) (un seul parcours de taille n)
2.
Pour chaque niveau i , l'algorithme fait 2n addition. Comme nous avons n-1 niveaux (voir figure), la
complexité est donnée par
0 1 n−1 n
T ( n)=2 +2 +............+2 =2 −1
il s'agit d'une suite géométrique de raison 2 et dont le premier terme est 1
La complexité est par conséquent O(2n )
