CPGEAL QALAM-AGADIR MP-PSI

COMPLEXITE ALGORITHMIQUE

 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=chaine.count('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?

 DEFINITION DE LA COMPLEXITE D'UN ALGORITHME

 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.
 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é?

Complexité -1 - M.GUEROIHI
 TYPES DE COMPLEXITE
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.
a- 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.
Dans ce type de complexité on trouve:
 Complexité en meilleur cas : c'est la valeur minimale des opérations effectuées par l'algorithme
 Complexité en pire des cas : c'est la valeur maximale des opérations effectuées par l'algorithme
 Complexité en moyenne : c'est la valeur moyenne des opérations effectuées par l'algorithme
b- Complexité spatiale (en espace)
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 en pire des cas.
 COMMENT MESURER LA COMPLEXITE D'UN ALGORITHME
a. Principe pour calculer la complexité d'un algorithme
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:
 Compter le nombre d'opérations jugées significatives : noté C(n) ou T(n). où n est le nombre de données
 Simplification du cout pour déduire la complexité en O (notation asymptotique/Landau (Grand O)). On
ne s'intéresse qu'au cas où n est très grand.

b. Le coût des instructions

 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 : + ; - ; * ; / ; %
Le coût d'une opération élémentaire est égal à 1.
Exemple1:
somme = n +1 #instr1 Coût = Coût(inst1)+Coût(instr2)+Coût(instr3)
somme = somme * n #instr2 = 2 +2 + 2
somme = somme/2 #instr3 =6
 Opération composée
On appelle opération composée, tout traitement contenant : une instruction conditionnelle, une boucle
ou l'appel d'une fonction:
 L'exécution d'une instruction conditionnelle :
if test :
Q1 Coût = Coût (test) + max (Coût(Q1) , Coût(Q2))
else:
Q2
Exemple2:
if i%2==0:
n=i//2 Coût = Coût(i%2==0)+max(Coût(n = i//2),Coût(i = i +1 , n = i//2))
else: Coût = 2 + max(2,4)
i=i+1 Coût = 6
n=i//2

Complexité -2 - M.GUEROIHI
  L'exécution d'une boucle :
o Boucle while

while condition: Coût= ∑(𝐂𝐨û𝐭(𝐜𝐨𝐧𝐝𝐢𝐭𝐢𝐨𝐧) + 𝐂𝐨û𝐭(𝒙𝒊 ))

𝒙𝒊 #bloc d'instructions

Exemple 3 :
i=1
s=0 Le corps de la boucle sera exécuté 𝑛 𝑓𝑜𝑖𝑠 (i varie de 1 à n) et la condition (i<=n) va
while i <= n : être exécutée une fois de plus (quand i=n+1)
s = s+i Coût = 𝟐 + ∑𝒏+𝟏 𝒏
𝒊=𝟏 𝑪𝒐𝒖𝒕(𝒊 ≤ 𝒏) + ∑𝒊=𝟏(𝑪𝒐𝒖𝒕(𝒔 = 𝒔 + 𝒊) + 𝑪𝒐𝒖𝒕(𝒊 = 𝒊 + 𝟏))
i = i+1
= 2 + (n+1) + n(2+2)
= 5n+3
o Boucle for

for i in range(n):
Coût= ∑(𝐂𝐨û𝐭(𝒙𝒊 ))
𝒙𝒊 #bloc d'instructions

Exemple 4 :
s=0
Coût= 1 + ∑𝒏−𝟏
𝒊=𝟎 (𝑪𝒐𝒖𝒕(𝒔 = 𝒔 + 𝒊))
for i in range(1,n+1):
s = s+i Coût= 2n+1

 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.

c. La notation O :
 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(.), notation
asymptotique/Landau (Grand O)).
Rappel : notation O
𝑠𝑜𝑖𝑒𝑛𝑡 𝒇 𝑒𝑡 𝒈 𝑑𝑒𝑢𝑥 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛𝑠 𝑑𝑒 ℕ ⟼ ℝ+

𝒇(𝒏) = 𝑶(𝒈(𝒏)) 𝐿𝑜𝑟𝑠𝑞𝑢𝑒 ∶ ∃ 𝑘 > 0 , ∃ 𝑛0 > 0 𝑡𝑒𝑙 𝑞𝑢𝑒 ∀ 𝑛 > 𝑛0 𝑓(𝑛) ≤ 𝑘 × 𝑔(𝑛)

Autrement dit : 𝒇(𝒏) 𝒆𝒔𝒕 𝒆𝒏 𝑶(𝒈(𝒏)) s'il existe un seuil à partir duquel la fonction 𝒇(. ) est toujours dominée
par la fonction 𝒈(. ), à une constante k multiplicative fixée près.
Exemples:
 3 2
Soit un algorithme effectuant C(n) = 4n - 5n +2n +3 opérations. On a alors C(n)=O(n
3
)
(Il suffit de garder le terme de plus grand ordre et supprimer son coefficient)

 C(n)=100n2 + 10n = O(n2)

 C(n) = n.log(n) + 12.n + 888 = O(n.log(n))
 C(n)=1000n−n+12n+(2n/100)=O(2n)
 Remarque
Si nous avons 𝒇𝟏(𝒏) = 𝑶(𝒈𝟏(𝒏)) 𝒆𝒕 𝒇𝟐(𝒏) = 𝑶(𝒈𝟐(𝒏)) , 𝒂𝒍𝒐𝒓𝒔 ∶
 𝒇𝟏(𝒏) + 𝒇𝟐(𝒏) = 𝑶(𝒈𝟏(𝒏) + 𝒈𝟐(𝒏))
 𝒇𝟏(𝒏). 𝒇𝟐(𝒏) = 𝑶(𝒈𝟏(𝒏). 𝑶(𝒈𝟐(𝒏)))

Complexité -3 - M.GUEROIHI
 CLASSES DE COMPLEXITE LES PLUS USUELLES
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

O(n) Linéaire
paramètre 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é par 4. 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
O(nk ) Polynômiale
voir des complexités en O(n3) ou O(n4).
quand le paramètre double, le temps d'exécution est élevé à la puissance k avec
O(kn) Exponentielle
k > 1.

O(n!) Factorielle asymptotiquement équivalente à nn

 EXEMPLES DE CALCUL DE COMPLEXITE

Exemple 1 Exemple 2
 La fonction suivante permet de retourner la somme
 La fonction suivante permet de retourner le
des éléments d’une liste:
quotient et le reste de la division d’un nombre
def Somme(L):
entier a par b. s=0
def division (a ,b): for i in range(len(L)) :
q=a//b s=s+L[i]
r=a%b return s
return(q,r) Exemple
 Exemple >>> L =[1, 2, 8, 4]

>>> x , y = 10 , 3 >>>Somme(L)

>>> division(x , y) 15

3 , 1  Le paramètre de complexité est la taille n de la

 Le nombre d'opérations est: 4 liste d'entrée L. on pose n=len(L)

 Temps de calcul est constant quelque soient a et b  Avant la boucle for on a une affectation

 Complexité: 𝓞(𝟏)  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)
 Le nombre total d'opérations est :
𝒏−𝟏

𝑪(𝒏) = 𝟏 + ∑ 𝟐 = 𝟐𝒏 + 𝟏
𝒊=𝟎

 Complexité: 𝓞(𝒏)

Complexité -4 - M.GUEROIHI
 Exemple 3 : Somme éléments d'une matrice

 La fonction suivante permet de retourner la somme des éléments d’une matrice carré M de dimensions n
lignes et n colonnes:
def Somme(M):
n=len(M)
s=0
for i in range(n) :
for j in range(n) :
s=s+M[i][j]
return s
Exemple
>>> M=[[1,2,3],[1,0,1],[6,4,5]]
>>> Somme(M)
23
 Le paramètre de complexité est n=len(M)
 Avant la boucle for on a 2 affectations et la fonction len(M)
 Le nombre total d'opérations est :
𝒏−𝟏 𝒏−𝟏

𝑪(𝒏) = 𝟑 + ∑ ∑ 𝟐 = 𝟑 + 𝟐𝒏𝟐
𝒊=𝟎 𝒋=𝟎

 Complexité: 𝓞(𝒏𝟐 )

Exemple 4 : 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 :

𝒏−𝟏 𝒏−𝟏 𝒏−𝟏

𝐓(𝐧) = 𝟔 + 𝐧 + 𝟏 + ∑ ∑ (𝟐 + ∑ 𝟑)
𝒊=𝟎 𝒋=𝟎 𝒌=𝟎

Complexité -5 - M.GUEROIHI
 𝒏−𝟏 𝒏−𝟏

𝐓(𝐧) = 𝟕 + 𝐧 + ∑ ∑(𝟐 + 𝟑. 𝒏)
𝒊=𝟎 𝒋=𝟎

𝒏−𝟏

𝐓(𝐧) = 𝟕 + 𝐧 + ∑(𝟐 + 𝟑. 𝒏). 𝒏

𝒊=𝟎

𝐓(𝐧) = 𝟕 + 𝐧 + ((𝟐 + 𝟑. 𝒏). 𝒏). 𝒏

𝑻(𝒏) = 𝟑𝒏𝟑 + 𝟐𝒏𝟐 +n+7

 Complexité: 𝓞(𝒏𝟑 )

Exemple 5 : recherches séquentielle

def Recherche_Seq(T,x):
n=len(T)
for i in range(n):
if T[i]==x :
return True
return False
 Le nombre d'opérations avant for est : 2
 La boucle for contient un test
 Le nombre de fois d'exécution de ce test dans le pire de cas est n
 Dans le pire des cas L’instruction return True ne sera jamais exécutée.
 Le nombre d'opérations total est :

𝒏−𝟏

𝐓(𝐧) = 𝟐 + ∑ 𝟏 = 𝒏 + 𝟐
𝒊=𝟎

 Complexité : 𝓞(𝒏)

Complexité -6 - M.GUEROIHI
 Exemple6 : 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]
 Le nombre d'opérations avant for est : 2
 Coût des échanges:
o 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:
o On recherche le minimum parmi n éléments : au plus 2(n -1) opérations. (c'est le nombre
d'itérations de la boucle sur j pour i fixé égal à n- 1)
o On recherche le minimum parmi n-1 éléments : au plus 2(n-2) opérations. (c'est le nombre
d'itérations de la boucle sur j pour i fixé égal à n-2)
o On recherche en suite le minimum parmi n-2 éléments: 2(n-3) tests.
o ...
 Le nombre total de tests est : 2(1+2+3+ … +(n- 2)+(n -1))=2( (n- 1)n)/2
 Le nombre total d'opérations est : T(n)=2+ 3(n- 1) + 2((n- 1)n)/2
𝐓(𝐧) = 𝒏𝟐 + 𝟐𝒏 − 𝟏
 Donc, la complexité est quadratique : 𝓞(𝒏𝟐 )
Autre façon de calcul.

𝒏−𝟐 𝒏−𝟏 𝒏−𝟐

𝐓(𝐧) = 𝟐 + ∑ (𝟑 + ∑ 𝟐) = 𝟐 + ∑(𝟑 + 𝟐(𝒏 − 𝒊 − 𝟏))

𝒊=𝟎 𝒋=𝒊+𝟏 𝒊=𝟎
𝒏−𝟐

𝐓(𝐧) = 𝟐 + ∑(𝟐𝒏 + 𝟏 − 𝟐𝒊)

𝒊=𝟎
𝒏−𝟐 𝒏−𝟐

𝐓(𝐧) = 𝟐 + ∑(𝟐𝒏 + 𝟏) − 𝟐. ∑ 𝒊
𝒊=𝟎 𝒊=𝟎
(𝒏 − 𝟐)(𝒏 − 𝟏)
𝐓(𝐧) = 𝟐 + (𝟐𝒏 + 𝟏)(𝒏 − 𝟏) − 𝟐. = 𝟐 + (𝟐𝒏 + 𝟏)(𝒏 − 𝟏) − (𝒏 − 𝟐)(𝒏 − 𝟏)
𝟐

𝐓(𝐧) = 𝟐 + (𝐧 − 𝟏) (𝟐𝐧 + 𝟏 − 𝐧 + 𝟐)
𝐓(𝐧) = 𝟐 + (𝒏 − 𝟏) (𝒏 + 𝟑)
𝐓(𝐧) = 𝟐 + 𝒏𝟐 + 𝟑𝒏 − 𝒏 − 𝟑
𝐓(𝐧) = 𝒏𝟐 + 𝟐𝒏 − 𝟏
Donc, la complexité est: 𝓞(𝒏𝟐 )

Complexité -7 - M.GUEROIHI
 Exemple 7 : 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
if 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 (après k divisions)

((((n/2)/2)/2)/…./2)=1

 Donc n/2k =1 et ainsi k=⌊𝐥𝐨𝐠 𝟐 (𝐧)⌋

 𝐓(𝐧) = 𝟒 + 𝒌 + 𝟏 + 𝒌(𝟑 + 𝟏 + 𝟏 + 𝟐)
 𝐓(𝐧) = 𝟖𝒌 + 𝟓 = 𝟖⌊𝐥𝐨𝐠 𝟐 (𝒏)⌋ + 𝟓
 Complexité: 𝓞(𝒍𝒐𝒈(𝒏))

Complexité -8 - M.GUEROIHI
  COMPLEXITE DES FONCTIONS RECURSIVES
 Écrire la fonction fact(n) qui reçoit en paramètre un entier positif n, et qui retourne la valeur de
factorielle n
version itérative version récursive
n! = 1 * 2 * 3 * … * (n-1) * n n! = n* (n-1) !
0!=1 0!=1

def fact (n): def fact (n):

f=1 if n==0:
for i in range (2, n+1): return 1
f=f*i else:
return f return n*fact(n-1)
 C(n) : nom d'opérations  C(n) : nom d'opérations
 Le nombre d'opérations avant for est : 1  Le cout du test est : 1
 Le nombre d'itérations de la boucle for est : n-1  Le cout du bloc else est: 𝐂(𝐧 − 𝟏) + 𝟐
et à chaque itération on exécute 2 opérations
𝐂(𝐧) = 𝟏 + 𝑪(𝒏 − 𝟏) + 𝟐
𝒏

𝐂(𝐧) = 𝟏 + ∑ 𝟐 = 𝟐𝒏 + 𝟏 𝐂(𝐧) = 𝑪(𝒏 − 𝟏) + 𝒃 𝒃 ∶ 𝒄𝒐𝒏𝒔𝒕𝒂𝒏𝒕𝒆

𝒊=𝟐 Pour calculer la solution générale de cette
𝐂(𝐧) = 𝚶(𝐧) : Complexité linéaire équation on peut procéder par substitution.

𝐂(𝐧) = 𝑪(𝒏 − 𝟏) + 𝒃
𝐂(𝐧) = [𝑪(𝒏 − 𝟐) + 𝒃] + 𝒃
𝐂(𝐧) = 𝑪(𝒏 − 𝟐) + 𝟐. 𝒃
𝐂(𝐧) = 𝑪(𝒏 − 𝟑) + 𝟑. 𝒃
.
.
.
𝐂(𝐧) = 𝐂(𝐧 − 𝐤) + 𝐤. 𝒃
𝐂(𝐧) = 𝐂(𝟎) + 𝐧. 𝒃
𝐂(𝐧) = 𝟏 + 𝐧. 𝒃
𝐂(𝐧) = 𝐧. 𝒃 + 𝟏
𝐂(𝐧) = 𝓞(𝒏): Complexité linéaire

Complexité -9 - M.GUEROIHI
  Écrire la fonction fib(n) qui reçoit en paramètre un entier positif n, et qui retourne le nième terme
de la suite de fibonacci définie par: 𝒇𝒊𝒃(𝟎) = 𝟎
𝒇𝒊𝒃(𝟏) = 𝟏
∀𝒏 ≥ 𝟐 , 𝒇𝒊𝒃(𝒏) = 𝒇𝒊𝒃(𝒏 − 𝟏) + 𝒇𝒊𝒃(𝒏 − 𝟐)
version itérative version récursive

def fib(n):
def fib(n):
if n<=1: return n
if n<=1:
a = 0
return n
b = 1
else:
for i in range(2,n+1):
return fib(n-1)+fib(n-2)
c=a+b
a=b  C(n) : nom d'opérations
b=c  Le cout du test est : 1
return c  Le cout du bloc else est:
𝐂(𝐧 − 𝟏) + 𝐂(𝐧 − 𝟐) + 𝟑
 C(n) : nom d'opérations Donc :
 Le nombre d'opérations avant for est : 3 𝑪(𝒏) = 𝑪(𝐧 − 𝟏) + 𝐂(𝐧 − 𝟐) + 𝟒 et 𝑪(𝟏) = 𝑪(𝟎) = 𝟏
 Le nombre d'itérations de la boucle for est : On pose : 𝑇(𝑛) = 𝐶(n) + 4
n-1 et à chaque itération on exécute 4
opérations Donc : 𝑇(𝑛) = 𝑇(n − 1) + 𝑇(𝑛 − 2) et 𝑇(1) = 𝑇(0) = 5
C'est une suite homogène dont l'équation caractéristique est :
𝒏
𝒙𝟐 − 𝒙 − 𝟏 = 𝟎 dont les racines sont :
𝐂(𝐧) = 𝟑 + ∑ 𝟒 = 𝟒𝒏 + 𝟑
1+√5 1−√5
𝒊=𝟐 𝑟= ≃ 1.6 et 𝑠= ≃ −0.6
2 2
𝐂(𝐧) = 𝓞(𝒏) : Complexité linéaire D'où ∃ 𝛼, 𝛽 ∈ ℝ , 𝑇(𝑛) = 𝛼. 𝑟 𝑛 + 𝛽. 𝑠 𝑛
𝐶(𝑛) = 𝑇(n) − 4
𝐶(𝑛) = 𝛼. 𝑟 𝑛 + 𝛽. 𝑠 𝑛 − 4
𝐶(𝑛) = 𝒪( 𝑟 𝑛 )
𝒏
𝟏+√𝟓
Donc 𝑪(𝒏) = 𝓞 (( 𝟐
) )
Complexité exponentielle (très mauvaise)

 Une autre méthode d'estimation de la complexité de la fonction fib(n) récursive.

𝑪(𝒏) = 𝑪(𝒏 − 𝟏) + 𝑪(𝒏 − 𝟐) + 𝟒
Si 𝒏 est grand, on pose : 𝑪(𝒏 − 𝟏) ≃ 𝑪(𝒏 − 𝟐) 𝑝𝑜𝑢𝑟 𝑛 = 𝑘 on a
𝐶(𝑛) = 2𝐶(𝑛 − 1) + 4 et 𝐶(1) = 𝐶(0) = 1 𝐶(𝑛) = 2𝑛 𝐶(0) + (2𝑛 − 1). 𝑏
C(n) = 2𝐶(𝑛 − 1) + 𝑏 𝒃 ∶ 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 𝑎𝑣𝑒𝑐 𝐶(0) = 1 𝑜𝑛 𝑎 ∶ 𝐶(𝑛) = 2𝑛 + (2𝑛 − 1). 𝑏
Par substitution successive, on a : 𝐶(𝑛) = 2𝑛 (𝑏 + 1) − 𝑏
𝐶(𝑛) = 2𝐶(𝑛 − 1) + 𝑏 = 2(2𝐶(𝑛 − 2) + 𝑏) + 𝑏 Donc 𝑪(𝒏) = 𝓞( 𝟐𝒏 )
𝐶(𝑛) = 4𝐶(𝑛 − 2) + 3. 𝑏 = 4(2𝐶(𝑛 − 3) + 𝑏) + 3. 𝑏 Complexité exponentielle (très mauvaise)
𝐶(𝑛) = 8𝐶(𝑛 − 3) + 7. 𝑏 = 8(2𝐶(𝑛 − 4) + 𝑏) + 7. 𝑏
𝐶(𝑛) = 16𝐶(𝑛 − 4) + 15. 𝑏
𝐶(𝑛) = 2𝑘 𝐶(𝑛 − 𝑘) + (2𝑘 − 1). 𝑏

Complexité -10 - M.GUEROIHI

 RESOLUTION DES EQUATIONS DE RECURRENCES SOUVENT RENCONTREES.
 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

---------------------------------------------------------Diviser pour régner------------------------------------------------------------------------

 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é -11 - M.GUEROIHI