CPGE-AGADIR MP-PSI-TSI
COMPLEXITE ALGORITHMIQUE
1. INTRODUCTION
Exercice
Ecrire en python une fonction qui prend en argument une chaîne de caractères et détermine si le caractère 'a' est
présent dans la chaîne (on retourne soit True soit False).
Analysons plusieurs solutions :
Première solution Deuxième solution
def contienta1(chaine): def contienta2(chaine):
k=0 for i in range(len(chaine)):
N=len(chaine) if chaine[i]=='a':
trouve=False return True
while(trouve == False and k < N): return False
if chaine[k]=='a':
trouve = True
k=k+1
return trouve
Troisième solution Quatrième solution
def contienta3(chaine): def contienta4 (chaine):
n=[Link]('a') return('a' in chaine)
return bool(n)
Quelques questions:
1. Le code le plus court ! Est-il meilleur?
2. Comment peut-on désigner le meilleur code parmi ces quatre solutions?
2. DÉFINITION DE LA COMPLEXITÉ D'UN ALGORITHME
La complexité d'un problème mathématiquePestunemesuredela quantité deressourcesnécessaires à la
résolutionduproblèmeP.
Cettemesureest baséesuruneestimationdunombre d'opérationsdebaseeffectuées
parl'algorithmeenfonctiondelatailledes donnéesen entréedel'algorithme.
Généralement,pour le même problèmeP,onpeuttrouverplusieursalgorithmes(Alg1; Alg2;...;Algn).
L'objectifdela complexité est d'évaluerlecoût d'exécutiondechaquealgorithmeafin de choisir le meilleur.
Problème:
Comment évaluer le coût d'exécution d'un algorithme donné?
Complexité 1 /9 [Link]
3. TYPES DE COMPLEXITÉ
En fonction des ressources utilisées pour évaluer la complexité d'un algorithme, on sera amené à distinguer deux
types de complexité: complexité temporelle et complexité spatiale.
Complexité temporelle (en temps)
La complexité temporelle d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons,
opérations arithmétiques) effectuées par un algorithme.
Complexité spatiale (enespace)
La complexité en mémoire donne le nombre d'emplacements mémoires occupés lors de l'exécution d'un
programme.
Remarque : Dans ce cours, nous nous intéressons uniquement à la complexité temporelle.
4. COMMENTMESURERLA COMPLEXITE D'UNALGORITHME
a. Principepourcalculerlacomplexité d'unalgorithme
La mesure de complexité d'un algorithme consiste à évaluer le temps d'exécution de cet algorithme.
Dans l'évaluation de ce temps d'exécution (coût), on sera amené à suivre les étapes suivantes:
Déterminer les opérations élémentaires(OE) à prendre en considération : T(OE).
Calculer le nombre d'instructions effectuées par les opérations composées(OC): T(OC).
Préciser les instructions à négliger.
Le coût de l'algorithme T(Alg) est la somme des deux coûts T(OE) et T(OC) : T(Alg)= T(OE) + T(OC)
Simplification du cout pour déduire la complexité O.
b. Le coût des instructions élémentaires
Opération élémentaire.
On appelle opération de base, ou opération élémentaire, toute:
Affectation;
Test de comparaison: ==;<;<=;>=;!=
Opération de lecture(input)et d’écriture (print);
Opération arithmétique:+;- ; *;/ ; %
Lecoûtd'uneopération élémentaireest égal à 1.
Exemple1: Que vaut le coût de l'algorithme A
somme = n +1 #instr1
somme = somme * n #instr2
somme = somme/2 #instr3
Coût(A) =Coût(inst1)+Coût(instr2)+Coût(instr3)
= 2 +2+2
=6
c. Le coût des instructions composées
Opérationcomposée
On appelle opération composée, toute instruction contenant:
L'exécution d'une instruction conditionnelle :
Si (test) alors
Q1
Sinon
Q2
Finsi
Le nombre d'opérations est:Coût(P) = Coût (test)+ max (Coût(Q1),Coût(Q2))
Complexité 2 /9 [Link]
L'exécutiond'uneboucle:
Le nombre d'opérations est égal à lamultiplicationdenombrederépétitionsparlasommedu
coûtdechaqueinstruction xi ducorpsdelaboucle;
Coût (bouclefor)= ∑ Coût (xi)
Coût(bouclewhile)= ∑ (Co ût (comparaison )+Coû t (xi) ¿ )¿
L'appeld'unefonction:Lorsqu'unefonctionouuneprocédureestappelée,lecoûtdecettefonctionouprocéd
ureestlenombretotald'opérations élémentairesengendréesparl'appeldecettefonction.
Exemple2: Que vaut le coût de l'algorithme B
ifi%2==0:
n=i//2
else:
i=i+1
n=i//2
Coût (B)=Coût(i%2==0)+max(Coût(n = i//2),Coût(i = i +1 , n = i//2))
= 2 + max(2,4)
=6
Exemple3: Que vaut le coût de l'algorithme C
i=1
while i <= n :
somme=somme+i
i=i+1
Coût(C)=1+ ∑ (Coût (i<¿ n)+Coû t (somme=somme +i)+ Coû t (i=i+1))
=1+n+2n+2n
=1+5n
d. La notation O :motivation
Les calculs à effectuer pour évaluer le temps d'exécution d'un algorithme peuvent parfois être longs et
pénibles;
De plus, ledegré de précision qu'ils requièrent est souvent inutile;
Onauradoncrecours à une approximation decetempsdecalcul,représenté parla notation O(.);
e. Règlesdecalcul:simplifications
On calcule le temps d'exécution comme avant, mais on effectue les simplifications suivantes:
o On oublie les constantes multiplicatives (elles valent 1);
o On annule les constantes additives;
o On ne retient que les termes dominants;
Exemple (simplifications)
Soit un algorithme effectuant T(n) = 4n3 - 5n2 +2n +3 opérations;
o On remplace les constantes multiplicatives par 1 : 1n3 - 1n2 + 1n +3
o On annule les constantes additives : n3 - n2 + n +0
o On garde le terme de plus haut degré : n3 + 0
3
Et on a donc : T(n)= O(n ).
Complexité 3 /9 [Link]
5. CLASSESDECOMPLEXITE LESPLUSUSUELLES
On voit souvent apparaître les complexités suivantes:
Complexité Nom courant Description
O(1) Constante Le temps d'exécution ne dépend pas des données traitées, ce qui est assez rare!
O(log(n)) Logarithmique augmentation très faible du temps d'exécution quand le paramètre croit.
augmentation linéaire du temps d'exécution quand le paramètre croit(si le paramètre
O(n) Linéaire
double, le temps double).
O(nlog(n)) Quasi-linéaire augmentation un peu supérieure à O(n)
quand le paramètre double, le temps d'exécution est multiplié par4. Exemple:
O(n2) Quadratique
algorithmes avec deux boucles imbriquées.
ici, nk est le terme de plus haut degré d'un polynôme en n ; il n'est pas rare de voir des
O(nk ) Polynômiale
complexités en O(n3) ou O(n4).
O(kn) Exponentielle quand le paramètre double, letemps d'exécution est élevé à la puissance k avec k > 1.
O(n!) Factorielle asymptotiquement équivalenteànn
6. EXEMPLES DE CALCUL DE COMPLEXITÉ
Exemple 1 Exemple 2
La fonction suivante permet de retourner le La fonction suivante permet de retourner la somme des
quotient et le reste de la division d’un nombre éléments d’une liste:
entier a par b. defSomme(L):
defdivision (a ,b): s=0
q=a//b for i in rang(len(L)) :
r=a%b s=s+L[i]
return(q,r) return s
Exemple Exemple
>>>x,y=10,3 >>> L =[1, 2, 8, 4]
>>>division(x , y) >>>Somme(L)
3 , 1 15
Le nombre d'opérationsest:5 Le paramètre de complexité est la taille n de
Tempsdecalculestconstant quelque soient a et b laliste d'entrée L. on pose n=len(L)
Complexité: O(1) en fixant i on exécute 2 opérations: (addition et
affectation)
Nombre de fois d'exécution de ces 2 opérations
est: n=len(T)
Lenombretotal d'opérationsest :
n −1
∑ 2+3=2 n+3
i=0
Complexité: O(n)
Complexité 4 /9 [Link]
Exemple 3 : rempliruntableau Exemple 4 : remplir une matrice
defRemplirTab (T): defRemplirMat(M):
n=len(M)
foriinrange(len(T)):
p=len(M[0])
print("T[",i, "]=",end=' ')
for i in range(n):
T[i]=int(input()) for j in range(p):
Le paramètre de complexité est la taille du print("T[",i,"][",j,"]=")
tableau d'entrée T. on pose n=len(T) T[i][j]=int(input())
en fixant i on exécute 4 opérations: (print, Coûtpoursaisirunevaleurest : 4
input,int et affectation) Lenombre d'itérationsdelabouclesur j pour ifixé
Nombre de fois d'exécution de ces 4 opérations égal à : p
est: n=len(T) Lenombretotalpourliretouteslesvaleurspour
Lenombretotal d'opérationsest : ifixéégal à 4p
n −1 Lenombretotal d'opérationsest :
∑ 4=4 n n−1 p−1
4 + ∑ ∑ 4=4+ 4 . n . p
i=0
Complexité: O(n) i=0 j=0
Complexité : O(n.p)
Si n=p, Complexité : O(n2)
Exemple 5 : Produit matriciel
defprodMatrice(A,B):
n=len(A) #nombre de lignes de A
m=len(A[0]) #nombre de colonne de A
p=len(B[0]) #nombre de colonnes de B
C=[p*[0] for i in range(n)]
for i in range(0,n):
for j in range (0,p):
s=0;
for k in range (0,m):
s = s + A[i][k]*B[k][j]
C[i][j]=s
return C
OnsupposequeAetBsontdeuxmatrices carréesd'ordren = m = p
Coûtpourcalculerunevaleurde s est :3(produit, addition etaffectation)
Lenombre d'itérations delabouclesur k pour j fixé égal àm=n
Lenombre d'itérations delabouclesur j pour i fixé égal àp=n
Lenombretotald'opérationsest :
( )
n−1 n−1 n−1
T (n)=6+ n+1+1+ ∑ ∑ 2+ ∑ 3
i=0 j=0 k=0
n−1 n−1
T (n)=8+ n+ ∑ ∑ (2¿+3. n¿)¿ ¿
i=0 j=0
Complexité 5 /9 [Link]
n−1
T ( n )=8+ n+∑ (2¿+ 3.n). n¿
i=0
T ( n )=8+ n+ ( ( 2+3. n ) . n ) .n
T ( n )=3 n3 +2 n2+n+8
Complexité: O(n3)
Exemple 6 : recherches séquentielle
defRecherche_Seq(T,x):
i=0
n=len(T)
for i in range(n):
if T[i]==x :
return True
return False
Lenombred'opérationsavantforest : 3
Laboucleforcontient2 opérations:(test et return True)
Lenombredefois d'exécutiondeces2instructions dans le pire de casest n
Lenombre d'opérations aprèsla boucle forest : 1(return False)
Lenombred'opérationstotalest :
n−1
T ( n )=4 + ∑ 2=2n+ 4
i=0
Complexité : O(n)
Complexité 6 /9 [Link]
Exemple7 : Tripar sélection
defTriSelection(T):
n=len(T)
for i in range(n-1):
Posmin=i
for j in range(i+1,n):
ifT[j]<T[Posmin]:
Posmin=j
#Permutation
T[i],T[Posmin]=T[Posmin],T[i]
Lenombred'opérationsavant for est : 2
Coût des échanges:
o Letripar sélectionsur n nombres fait n-1 échanges,cequifait : 3(n- 1)affectations
Coûtdesrecherchesde minimum:
o Onrecherchele minimumparmi n éléments:auplus2(n -1)opérations.(c'estlenombre
d'itérations delabouclesur j pour i fixé égal à n- 1)
o Onrecherchele minimum parmi n-1 éléments:auplus2(n-2) opérations.(c'estlenombre
d'itérations delabouclesur j pour i fixé égal à n-2)
o Onrechercheensuitele minimumparmi n-2 éléments:2(n-3)tests.
o ...
Lenombretotaldetestsest : 2(1+2+3+ … +(n- 2)+(n -1))=2( (n- 1)n)/2
Lenombretotal d'opérationsest:T(n)=2+3(n- 1) + 2((n- 1)n)/2
2
T ( n )=n +2 n−1
Donc,lacomplexité estquadratique : O(n2)
Autre façon de calcul.
( )
n−2 n −1 n−2
T ( n )=2+ ∑ 3+ ∑ 2 =2+ ∑ ( 3+2(n−i−1) )
i=0 j =i +1 i=0
n−2
T ( n )=2+ ∑ ( 2 n+1−2i )
i=0
n−2 n−2
T ( n )=2+ ∑ ( 2 n+1 ) −2. ∑ i
i=0 i=0
( n−2 ) ( n−1 )
T ( n )=2+ ( 2 n+1 ) ( n−1 )−2. =2+ ( 2 n+1 ) ( n−1 )−( n−2 ) ( n−1 )
2
T ( n )=2+ ( n−1 ) (2 n+1−n+2 )
T ( n )=2+ ( n−1 ) ( n+3 )
2
T ( n )=2+n +3 n−n−3
2
T ( n )=n +2 n−1
Donc,lacomplexité est: O(n2)
Complexité 7 /9 [Link]
Exemple 8 : Recherchedichotomique
defRechDichotomique(T,x):
g,d=0,len(T)-1
whileg<=d:
m=(g+d)//2
ifT[m]==x: returnTrue
ifT[m]<x:
g=m+1
else:
d=m-1
returnFalse
Soit k le nombre de passages dans la boucle while.
on divise le nombre d'éléments restants par 2jusqu'à ce qu'il n'en reste qu'un (k divisions)
((((n/2)/2)/2)/…./2)=1
Donc n/2k =1 et ainsi k=log2n
Complexité: O(log2(n))
Exemple 9 : lestoursde Hanoï
defhanoi (n , A='A' , B='B', C='C'):
if n > 0:
hanoi(n-1, A, C, B)
print("Déplacer le disque %d de la tige %s vers la tige %s."% (n, A, C))
hanoi(n-1, B, A, C)
L'évaluation de la complexité de cet algorithme est assez simple. Nous allons chercher à savoir combien de
déplacements de disques sont nécessaires pour arriver à nos fins. Très simplement, la fonction calculant ceci
peut être définie de la manière suivante (on peut se baser sur la fonction ci-dessus) :
T(0) = 0; T(1) = 1; T(n) = 2*T(n-1)+1. On peut démontrer par récurrence que ceci est égal à T(n) = 2n-1 :
On a T(n+1) = 2*T(n)+1. En supposant que T(n) = 2 n-1, on a T(n+1) = 2*(2n-1)+1. On développe ensuite en
T(n+1) = 2*2n -2+1 ce qui nous donne au final T(n+1) = 2 n+1-1. On a ainsi démontré que si c'est vrai pour n,
alors c'est vrai pour (n+1). Comme on a T(1) = 2*0+1 = 2 1-1 = 1, c'est vrai pour tous les n supérieurs à 1. La
complexité exacte de l'algorithme présenté ci-dessus est donc en 2n-1 pour n disques à déplacer de la tour
On trouve T(n)=2n - 1
Donc lacomplexité est éxponentielle O(2n)
Complexité 8 /9 [Link]
7. COMPLEXITÉ ET RÉCURSIVITÉ
Il existe diverses techniques pour la résolution des équations de récurrence.
méthode des fonctions génératrices et décomposition des fractions rationnelles
Transformée en Z
…
Résolution des récurrences.
C(n) = C(n-1) + b
solution : C(n) = c(0) + b*n = O(n)
exemples : factorielle, recherche séquentielle récursive dans un tableau
C(n) = a*C(n-1) + b, a ≠ 1
solution : C(n) = an*(C(0) – b/(1-a)) + b/(1-a) = O(an)
exemples : répétition a fois d'un traitement sur le résultat de l'appel récursif
C(n) = C(n-1) + a*n + b
solution : C(n) = c(0) + a*n*(n+1)/2 + n*b = O(n2).
exemples : traitement en coût linéaire avant l'appel récursif, tri à bulle
C(n) = C(n/2) + b
solution : C(n) = C(1) + b*log2(n) = O(log(n))
exemples : élimination de la moitié des éléments en temps constant avant l'appel récursif, recherche
dichotomique récursive
C(n) = a*C(n/2) + b, a ≠ 1
solution : C(n) = nlog2(a) *(c(1) – b/(1-a)) + b/(1-a) = O(nlog2(a))
exemples : répétition a fois d'un traitement sur le résultat de l'appel récursif dichotomique
C(n) = C(n/2) + n
solution : C(n) = O(n)
exemples : traitement linéaire avant l'appel récursif dichotomique
C(n) = 2*C(n/2) + a*n + b
solution : C(n) = O(n*log(n))
exemples : traitement linéaire avant double appel récursif dichotomique, tri fusion
Complexité 9 /9 [Link]