Complexité algorithmique
Exercice 1
Ecrire en python une fonction qui prend en argument une chaîne de caractères et
détermine si la chaîne est palindrome ou non.
Exemple: '11000011' est palindrome 'information' n'est pas palindrome
def Palindrome1(ch):
n=len(ch)
for i in range(n//2):
if ch[i]!=ch[n-1-i]:
return False
return True
def Palindrome2(ch):
n=len(ch)
for i in range(n):
if ch[i]!=ch[n-1-i]:
return False
return True
import numpy as np
ch="".join('a' for i in range(10000000))
%time Palindrome1(ch)
%time Palindrome2(ch)
CPU times: total: 734 ms
Wall time: 734 ms
CPU times: total: 1.28 s
Wall time: 1.28 s
True
Exercice 2
• Ecrire une fonction qui calcule la valeur d'un polynome en un point x 0 (Les coefficients
sont donnés dans un tableau comme paramètre de la fonction)
• Ecrire une fonction qui calcule la valeur d'un polynome en un point x 0 basant sur la
méthode de Horner
n
P ( x )=∑ a k x k =a0 + x ( a 1+ x ( a2+ . ..+ x ( an − 1+ x a n) ) .. . )
k=0
• Comparer les deux fonctions en terme de temps d'exécution.
##### Calcul de polynome par 'algorthme de Horner
def polynome(P,x):
n=len(P)
p=0
for i in range(n):
p+=P[i]*x**i
return p
def Horner(P,x):
n=len(P)
p=P[n-1]
for i in range(n-2,-1,-1):
p=p*x+P[i]
return p
import numpy as np
P=[np.random.randint(9) for i in range(10)]
%time Horner(P,2)
%time polynome(P,2)
CPU times: total: 0 ns
Wall time: 0 ns
CPU times: total: 0 ns
Wall time: 0 ns
2854
Puissance_Reduite(2,7)
128
Exercice 3
• Ecrire une fonction qui calcule la puissance : x n
• Ecrire une fonction qui calcule la puissance x n par cette méthode:
def puissanceRec(x,n):
if n==0:
return 1
y=puissanceRec1(x,n//2)
if n%2==0:
P=y*y
else:
P=y*y*x
return P
def puissance_Reduite(x,n):
p=1
while(n!=0):
if n%2!=0:
p=p*x
x=x*x
n=n//2
return p
def puissance(x,n):
p=1
for i in range(n):
p=p*x
return p
n=1000
%time puissanceRec(2,n)
%time puissance_Reduite(2,n)
%time puissance(2,n)
CPU times: total: 0 ns
Wall time: 0 ns
CPU times: total: 0 ns
Wall time: 0 ns
CPU times: total: 0 ns
Wall time: 995 µs
1071508607186267320948425049060001810561404811705533607443750388370351
0511249361224931983788156958581275946729175531468251871452856923140435
9845775746985748039345677748242309854210746050623711418779541821530464
7498358194126739876755916554394607706291457119647768654216766042983165
2624386837205668069376
• La complexité d'un problème mathématique P est une mesure de la quantité de
ressources nécessaires à la résolution du problème P.
Cette mesure est basée sur:
• Une estimation du nombre d'opérations de base effectuées par l'algorithme en
fonction de la taille des données en entrée de l'algorithme.
• Une estimation des allocations mémoires necessaires pour resoudre le problème P
– Généralement, pour le même problème P, on peut trouver plusieurs algorithmes
(Alg1; Alg2;...;Algn).
– L'objectif de la complexité est d'évaluer le coût d'exécution de chaque algorithme
afin de choisir le meilleur.
Problème:
Comment évaluer le coût d'exécution d'un algorithme donné?
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.
• La complexité temporelle d'un algorithme est le nombre d'opérations élémentaires
(affectations, comparaisons, opérations arithmétiques ou logiques) effectuées par un
algorithme.
• La complexité en mémoire donne le nombre d'emplacements mémoires occupés lors de
l'exécution d'un programme.
• On va s'interesser à la complexité temporelle càd le nombre d'instructions élémentaires
a) Le coût des instructions élémentaires
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:+;- ; *;/ ; %
Le coût d'une opération élémentaireest égal à 1.
Exemple1: Que vaut le coût de l'algorithme A
b)- Le coût des instructions composées(Si)
• L'exécution d'une instruction conditionnelle : Si (test) alors Q1 Sinon Q2 Finsi
Le nombre d'opérations est: C o ût ( P )=C o ût ( t e s t ) +m a x ( C oû t ( Q1 ) , C o û t ( Q 2 ) )
c)- Le coût des instructions composées(Boucle)
L'exécution d'une boucle : est égal à la multiplication de nombre de répétitions par la
somme du coût de chaque instruction x i du corps de la boucle
• Boucle Pour : Coût(Boucle for)=$\sum \limits {} ^{} Coût(x{i}) $
• Boucle Tant que : Coût(Boucle while)=$\sum \limits {} ^{} (Coût(x{i})
+Coût(comparaison)) $
L'appel d'une fonction : Lorsqu'une fonction ou une procédure est appelée, le coût de
cette fonction ou procédure est le nombre total d'opérations élémentaires engendrées
par l'appel de cette fonction.
Exemple2: Que vaut le coût de l'algorithme B
if i%2==0:
n=i//2
else:
i=i+1
n=i//2
Exemple3: Que vaut le coût de l'algorithme C
i=1
while i <= n :
somme=somme+i
i=i+1
Exemple2
C o ût ( B )=C o û t (i % 2=¿ 0 ) +m a x ( C o û t ( n=i/¿ 2 ) , C o û t (i=i+1 , n=i/¿ 2 ) ) =2+m a x ( 2 , 4 )=6
Exemple3
C o ût ( C ) =1+ ∑ ( C o û t (i<¿ n )+ C o û t ( s o m m e=s o mm e+i ) +C o û t ( i=i+1 ) )
¿ 1+n+2 n+2 n=1+5 n
a) Motivation
• Les calculs à effectuer pour évaluer le temps d'exécution d'un
algorithme peuvent
parfois être longs et pénibles;
• De plus, le degré de précision qu'ils requièrent est souvent
inutile;
• On aura donc recours à une approximation de ce temps de
calcul,représenté par la
notation O(.)
Exemple 1: Prouvons que la fonction T ( n )=3 n+6 est en O ( n ) (on écrit aussi $(3n+6) \in O(n)) $
Trouver une constante c et un seuil n 0 à partir du quel T ( n )< ¿ c . n On remarque : 3 n+6< ¿ 9 n si
n> ¿2
3 ∗2+ 6<¿ 9 ∗ 2
3 ∗3+ 6<¿ 9 ∗ 3
3 ∗ 4+ 6<¿ 9 ∗ 4
3 ∗5+ 6<¿ 9 ∗ 5
Remarque: On ne demande pas d’optimisation (le plus petit c ou n 0 qui fonctionne), juste de
donner des valeurs qui fonctionnent ; c=10 et n 0=5 est donc aussi acceptable ;
Exemple 2: prouvons que la fonction T ( n )=n2 +3 n est en O ( n2 )
But : Trouver une constante c et un seuil n 0 à partir du quel T ( n )< ¿ c . n2
• On cherchons d’abord la constante c ; c=1 ne peut pas marcher, essayons donc c=2
• On doit trouver un seuil n 0 à partir du quel n2 +3 n< ¿2 n 2
• On remarque n2 +3 n< ¿2 n 2 si n> ¿3
• On déduit que c=2 fonctionne à partir d’un seuil n 0=3
Comparaison de temps d’exécution
Règles de calcul de la comlexité: simplifications
• On calcule le temps d'exécution comme avant, mais on effectue les
simplifications suivantes:
◦ On oublie les constantes multiplicatives (elles valent 1);
◦ On annule les constantes additives;
◦ On ne retient que les termes dominants;
• Exemple (simplifications)
Soit un algorithme effectuant T ( n )=4 n3 −5 n2 +2 n+3 opérations;
• On remplace les constantes multiplicatives par 1 : 1 n3 − 1 n2+ 1n+ 3
• On annule les constantes additives : n3 −n 2+ n+0
• On garde le terme de plus haut degré : n3 +0 et on a donc : T ( n )=O ( n3 ).
• Exemple 1:
def Somme(L):
s=0
n=len(L)
for i in rang(n) :
s=s+L[i]
return s
Exemple
>>> L =[1, 2, 8, 4]
>>>Somme(L)
15
• Le paramètre de complexité est la taille de la liste d'entrée L.
• en fixant i on exécute 2 opérations: (addition et affectation)
• Nombre de fois d'exécution de ces 2 opérations est: l e n ( T )
• Le nombre total d'opérations est : 2∗le n ( L )+3
• Complexité: O ( l e n ( L ) )=O ( n )
• Exemple 3:
def RemplirTab (T):
for i in range(len(T)):
print("T[",i, "]=",end=' ')
T[i]=int(input())
• Le paramètre de complexité est la taille du tableau d'entrée T.
• en fixant i on exécute 4 opérations: (print, input,int et affectation)
• Nombre de fois d'exécution de ces 4 opérations est: l e n ( T )
• Le nombre total d'opérations est : 4∗le n (T )
• Complexité: O ( l e n ( T ) ) =O ( n )
• Exemple 4:
def RemplirMat(M):
n=len(M)
p=len(M[0])
for i in range(n):
for j in range(p):
print("M[",i,"][",j,"]=")
M[i][j]=int(input())
• Coût pour saisir une valeur est : 4
• Le nombre d'itérations de la boucle sur j pour i fixé égal à : p
• Le nombre total pour lire toutes les valeurs pour i fixé égal à 4 p
• Le nombre total d'opérations est : 2+ 4 p .n
• Complexité : O ( n . p )
• Exemple 5 : Produit matriciel
def prodMatrice(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
• On suppose que A et B sont deux matrices carrées d'ordre n=m= p
• Coût pour calculer une valeur de s est : 3(produit, addition et affectation)
• Le nombre d'itérations de la boucle sur k pour j fixé égal à m=n
• Le nombre d'itérations de la boucle sur j pour i fixé égal à p=n
• Le nombre total d'opérations est : T ( n )=4 +n+ n ( n ( 2+ 3 n ) )
• Complexité: O ( n3 )
• Exemple 6 : Tri par sélection
def TriSelection(T):
n=len(T)
for i in range(n-1):
Posmin=i
for j in range(i+1,n):
if T[j]<T[Posmin]:
Posmin=j
#Permutation
T[i],T[Posmin]=T[Posmin],T[i]
• Coût des échanges: le tri par sélection sur n nombres fait n −1 échanges, ce qui fait :
3 ( n −1 ) affectations
• Coût des recherches de minimum:
– Le nombre total des tests est : 2 ( 1+2+3+…+ ( n− 2 ) + ( n −1 ) ) =n ( n −1 )
– Le nombre total de recherche minimum : n ( n −1 ) + ( n− 1 )
• Le nombre total d'opérations est : 3 ( n −1 ) + ( n −1 )+ n ( n− 1 )=n ( n −1 )+ 4 ( n −1 )
• Donc, la complexité est quadratique : O ( n2 )
• Exemple 7: recherches séquentielle
def Recherche_Seq(T,x):
i=0
n=len(T)
for i in range(n):
if T[i]==x :
return True
return False
• Le nombre d'opérations avant for est : 3
• La boucle for contient une opération : test
• Le nombre de fois d'exécution de l'instruction de test dans le pire de cas est n
• Une opération de (return True)
• Le nombre d'opérations après la boucle for est : 1(return False)
• Le nombre d'opérations total est : 3+n+ 1
• Complexité : O ( n )
• Exemple 8 : Recherche dichotomique
def RechDichotomique(T,x):
g,d=0,len(T)-1
while g <= d:
m=(g+d)//2
if T[m]==x:
return True
elif T[m]<x:
g=m+1
else:
d=m-1
return False
• Soit k le nombre de passages dans la boucle while.
• On divise le nombre d'éléments restants par 2 jusqu'à ce qu'il n'en reste qu'un élément(k
divisions) ( ( ( ( n / 2 ) / 2 ) / 2 ) /… ./ 2 )=1
n
• Donc k
=1 et ainsi k =log 2 ( n )
2
• Complexité : O ( log 2 ( n ) )
On distingue 3 types de complexités: Complexité au pire des cas, dans le meilleur des cas et en
moyenne des cas.
7-1 : Complexité au pire des cas
La complexité au pire des cas est le plus grand nombre d'opérations qu'aura à exécuter
l'algorithme sur un jeu de données de taille fixée à n.
T m a x ( n )=max {C ( d ) }
d ∈ Dn
• Dn Ensemble des données de taille n
• C ( d ) est le coût d'exécution de l'algorithme sur la donnée d
Exemple: Recherche d'un élément dans un tableau
def find(T,x):
n=len(T)
for i in range(n):
if T[i]==x:
return True
return False
• On note n la longueur du tableau T ( n=l e n ( T ) ).
• Dans le pire des cas : quand l'élément recherché x est le dernier (dans la case n-1) ou est
absent.
• Donc la complexité dans le pire est $C_{max} (n)= n $
7-2 : Complexité dans le meilleur des cas
La complexité au meilleur est le plus petit nombre d'opérations qu'aura à exécuter l'algorithme
sur un jeu de données de taille fixée. C'est une borne inférieure de la complexité de l'algorithme
sur un jeu de données de taille n.
T m i n ( n )= min {C ( d ) }
d∈Dn
Exemple: Recherche d'un élément dans un tableau
• On considère le même exemple précédent.
• Dans le meilleur des cas : quand l'élément recherché x se trouve en 1ere position.
• Donc la complexité dans le meilleur des cas est : C m i n ( n )=1
7-3 : Complexité dans le cas moyen
La complexité en moyenne est la moyenne des complexités de l'algorithme sur des jeux de
données de taille n .
T m o y ( n )=∑ { Pr ( d ) . C ( d ) }d ∈ D n
Cette complexité en moyenne reflète le comportement "général" de l'algorithme si les cas
extrêmes sont rares ou si la complexité varie peu en fonction des données.
• Où P r ( d ) est la probabilité d'avoir la donnée d en entrée de l'algorithme.
• C ( d ) est le coût d'exécution de l'algorithme sur la donnée d
Exemple : Recherche d'un élément dans un tableau
def find(T,x):
n=len(T)
for i in range(n):
if T[i]==x:
return True
return False
En moyenne, dans l'hypothèse où la probabilité de trouver x dans le tableau est q et si x est
1
présent, il peut se trouver dans n'importe quelle case avec la même probabilité, à savoir
n
i
Alors la probabilité que x se trouve dans la ième case est :q . , d'où:
n
C m o y ( n )=q . ( 1n + 2n + 3n + …+ nn )+( 1 −q ) . n=q . ( n+12 ) + (1 − q) . n
( n+1 )
Si q=1 la complexité en moyenne des cas sera C m o y ( n )=
2
Exemple
def factoriel(n) :
if (n == 0) :
return 1
return n*factoriel(n-1)
Soit c ( n ) la nombre de multiplications effectuées dans le calcul de factoriel(n). On a
C ( n )=C ( n − 1 )+ 1+1+1=C ( n −1 )+3=C ( 0 )+ 3 n=O ( n ) , C ( 0 )=1
Résolution des récurrences:
$C(n) = C(n-1) + b $
• Solution : C ( n )=C ( 0 )+ b∗n=O ( n )
• factorielle, recherche séquentielle récursive dans un tableau
$C(n) = a.C(n-1) + b ; ; a ≠ 1 $
•
n
(
solution : C ( n )=a C ( 0 )+
b
−
b
)
a −1 a− 1
=O ( an )
• répétition a fois d'un traitement sur le résultat de l'appel récursif
C ( n )=C ( n − 1 )+ C ( n −2 )
1+ √ 5
• La résolution de l'équation caractéristique r 2 −r −1=0 qui donne deux racines ϕ=
2
1 −√5
et ϕ ′=
2
• La complexité est de la fomre: α ϕ n+ β ϕ ′ n=O ( ϕ n)
Exemple
def Fibonacci(n):
if n<=1:
return 1
return Fibonacci(n-1)+Fibonacci(n-2)
C ( n )=C ( n − 1 )+ C ( n −2 ) +O ( 1 )
La complexité
1+ √ 5
• La résolution de l'équation caractéristique r 2 −r −1=0 qui donne deux racines ϕ=
2
1 −√5
et ϕ ′=
2
• La complexité est de la fomre: α ϕ n+ β ϕ ′ n=O ( ϕ n)
Fibonacci(6)
C ( n )=C ( n − 1 )+ a∗n+b
a∗n∗n+1
+ n∗b=O ( n )
2
• solution : C ( n )=c ( 0 ) +
2
• exemples : traitement en coût linéaire avant l'appel récursif
C ( n )=C ( n /2 )+ b
• solution : C ( n )=C ( 1 ) +b∗log 2 ( n )=O ( log 2 ( n ) )
• exemples : élimination de la moitié des éléments en temps constant avant l'appel
récursif, recherche dichotomique récursive
C ( n )=2 C ( n/2 ) +b
• solution : C ( n )=O ( n log 2 ( n ) )
• exemples : Tri par fusion
C ( n )=C ( n2 )+n
• solution : C ( n )=O ( n )
Exemple
def f(x, n):
if n < 1:
return n
S = 0
for i in range(0,n): # O(n)
S += x/(i+n)
return S + f(x,n/2) #O(log(n))
C ( n )=C ( n /2 )+ α n+ β=O ( n )
Exercice 1
def Algo(n):
res = 1;
for i in range(0,n):
res = res + i
for i in range(0,n):
for j in range(0,i):
res = res * (i+j)
return res
Solution
Complexité : O ( n2 )
Exercice 2
def f1(A,x) :
n =len(A)
p=A[0]
for i in range(1,n) :
p = p + A[i]*x**i
return p
Complexité O ( n2 )
Exercice 3
def SupprimerElement(L,a):
i=0
if a in L: #O(n)
while L[i]!=a: #O(n)
i=i+1
L[i:i+1]=[]
Complexité O ( n )
