Cours 2 Composition d’Algorithmes et
Complexité
Conceptes Fondamentaux
Prof Kaninda Musumbu
1 Université de Bordeaux & ESIS - Salama (RDC)
K Musumbu Composition d’Algorithmes
Introduction
Objectif :
Éviter la duplication de code en utilisant un mécanisme
similaire à la composition de fonctions en mathématiques.
Une fonction :
soit “modifie les variables” du programme, soit “retourne un
résultat” ; dans les deux cas, cette fonction peut être utilisée
soit comme une instruction,
soit comme une expression.
K Musumbu Composition d’Algorithmes
Introduction
Objectif :
Éviter la duplication de code en utilisant un mécanisme
similaire à la composition de fonctions en mathématiques.
Une fonction :
soit “modifie les variables” du programme, soit “retourne un
résultat” ; dans les deux cas, cette fonction peut être utilisée
soit comme une instruction,
soit comme une expression.
K Musumbu Composition d’Algorithmes
Introduction
Objectif :
Éviter la duplication de code en utilisant un mécanisme
similaire à la composition de fonctions en mathématiques.
Une fonction :
soit “modifie les variables” du programme, soit “retourne un
résultat” ; dans les deux cas, cette fonction peut être utilisée
soit comme une instruction,
soit comme une expression.
K Musumbu Composition d’Algorithmes
Introduction
Objectif :
Éviter la duplication de code en utilisant un mécanisme
similaire à la composition de fonctions en mathématiques.
Une fonction :
soit “modifie les variables” du programme, soit “retourne un
résultat” ; dans les deux cas, cette fonction peut être utilisée
soit comme une instruction,
soit comme une expression.
K Musumbu Composition d’Algorithmes
Introduction
Objectif :
Éviter la duplication de code en utilisant un mécanisme
similaire à la composition de fonctions en mathématiques.
Une fonction :
soit “modifie les variables” du programme, soit “retourne un
résultat” ; dans les deux cas, cette fonction peut être utilisée
soit comme une instruction,
soit comme une expression.
K Musumbu Composition d’Algorithmes
Complexité
objectifs
Estimer le temps (ou l’espace) requis par l’exécution d’un
algorithme lorsque les données en entrée deviennent très
grandes.
Définitions
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme. On note T (n) la
fonction qui associe à la taille n des données le temps (ou
l’espace) requis par l’exécution de T .
T a une complexité dite au pire des cas en O(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≤ c × f (n)
T a une complexité dite au meilleur des cas en Ω(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≥ c × f (n)
K Musumbu Composition d’Algorithmes
Complexité
objectifs
Estimer le temps (ou l’espace) requis par l’exécution d’un
algorithme lorsque les données en entrée deviennent très
grandes.
Définitions
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme. On note T (n) la
fonction qui associe à la taille n des données le temps (ou
l’espace) requis par l’exécution de T .
T a une complexité dite au pire des cas en O(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≤ c × f (n)
T a une complexité dite au meilleur des cas en Ω(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≥ c × f (n)
K Musumbu Composition d’Algorithmes
Complexité
objectifs
Estimer le temps (ou l’espace) requis par l’exécution d’un
algorithme lorsque les données en entrée deviennent très
grandes.
Définitions
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme. On note T (n) la
fonction qui associe à la taille n des données le temps (ou
l’espace) requis par l’exécution de T .
T a une complexité dite au pire des cas en O(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≤ c × f (n)
T a une complexité dite au meilleur des cas en Ω(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≥ c × f (n)
K Musumbu Composition d’Algorithmes
Complexité
objectifs
Estimer le temps (ou l’espace) requis par l’exécution d’un
algorithme lorsque les données en entrée deviennent très
grandes.
Définitions
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme. On note T (n) la
fonction qui associe à la taille n des données le temps (ou
l’espace) requis par l’exécution de T .
T a une complexité dite au pire des cas en O(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≤ c × f (n)
T a une complexité dite au meilleur des cas en Ω(f (n)) si
∃n0 , ∃c tel que ∀n > n0 , T (n) ≥ c × f (n)
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Complexités classiques
Constante : f (n) = 1
Logarithmique : f (n) = ln(n) ou bien f (n) = log2 (n) ou bien
f (n) = logb (n)
Linéaire : f (n) = n
Quadratique : f (n) = n2
Polynomiale : f (n) = np
p-Exponentielle : f (n) = pn
Factorielle : n!
K Musumbu Composition d’Algorithmes
Complexité
Un ordre sur les complexités
Constante < Logarithmique < Linéaire < Quadratique <
Polynomiale < p-Exponentielle < Factorielle.
min(Linéaire, Quadratique) = Linéaire
max(Linéaire, Quadratique) = Quadratique
Propriété
g(n) = O(f (n)) ⇔ f (n) = Ω(g(n))
K Musumbu Composition d’Algorithmes
Complexité
Un ordre sur les complexités
Constante < Logarithmique < Linéaire < Quadratique <
Polynomiale < p-Exponentielle < Factorielle.
min(Linéaire, Quadratique) = Linéaire
max(Linéaire, Quadratique) = Quadratique
Propriété
g(n) = O(f (n)) ⇔ f (n) = Ω(g(n))
K Musumbu Composition d’Algorithmes
Complexité
Un ordre sur les complexités
Constante < Logarithmique < Linéaire < Quadratique <
Polynomiale < p-Exponentielle < Factorielle.
min(Linéaire, Quadratique) = Linéaire
max(Linéaire, Quadratique) = Quadratique
Propriété
g(n) = O(f (n)) ⇔ f (n) = Ω(g(n))
K Musumbu Composition d’Algorithmes
Complexité
Un ordre sur les complexités
Constante < Logarithmique < Linéaire < Quadratique <
Polynomiale < p-Exponentielle < Factorielle.
min(Linéaire, Quadratique) = Linéaire
max(Linéaire, Quadratique) = Quadratique
Propriété
g(n) = O(f (n)) ⇔ f (n) = Ω(g(n))
K Musumbu Composition d’Algorithmes
Complexité
Un ordre sur les complexités
Constante < Logarithmique < Linéaire < Quadratique <
Polynomiale < p-Exponentielle < Factorielle.
min(Linéaire, Quadratique) = Linéaire
max(Linéaire, Quadratique) = Quadratique
Propriété
g(n) = O(f (n)) ⇔ f (n) = Ω(g(n))
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Définition
Soit T un algorithme et n un entier qui représente la “taille” des
données passées en paramètre à l’algorithme.
T a une complexité dite exacte en Θ(f (n)) si T est d’une
part en O(f (n)) ; d’autre part en Ω(f (n)).
Complexité d’un algorithme
De façon simplifiée, un ordinateur dispose de trois types
d’instructions s’exécutant chacune dans un temps constant.
lecture (LOAD) en temps tlec : c’est le transfert de la
mémoire vers un registre.
calcul en temps tcal : c’est l’évaluation des expressions et
notamment des prédicats.
écriture (SAVE) en temps tecr : c’est le transfert d’un
registre vers la mémoire.
K Musumbu Composition d’Algorithmes
Complexité
Le temps mis par l’exécution d’un algorithme est donc :
(]lec × tlec ) + (]cal × tcal ) + (]ecr × tecr )
En général
tlec tcal tecr , uneapproximationdutempsestalors(]ecr × tecr )
Dans ce cours, on considérera
tlec {tcal , tecr },
une approximation du temps est alors
((]cal + ]ecr ) × tecr ).
En complexité, les coefficients multiplicateurs ne sont pas
retenus (ici tecr ).
K Musumbu Composition d’Algorithmes
Complexité
Analyse de complexité en temps
consiste donc à évaluer Tt (n) = (]cal + ]ecr ).
l’espace requis par l’exécution d’un algorithme est donc :
(]data + ]prog + ]aux
Analyse de complexité en espace
consiste à évaluer
Te (n) = (]aux ).
K Musumbu Composition d’Algorithmes
Complexité
Analyse de complexité en temps
consiste donc à évaluer Tt (n) = (]cal + ]ecr ).
l’espace requis par l’exécution d’un algorithme est donc :
(]data + ]prog + ]aux
Analyse de complexité en espace
consiste à évaluer
Te (n) = (]aux ).
K Musumbu Composition d’Algorithmes
Structure de données
Un tableau T : type[n]
est une structure de données qui contient n variables de
même type, chacune accessible par un indice compris
entre 0 et n − 1.
Par exemple T : entier[10] défini un tableau de 10
variables entières T[0], ..., T[9].
K Musumbu Composition d’Algorithmes
Structure de données
Un tableau T : type[n]
est une structure de données qui contient n variables de
même type, chacune accessible par un indice compris
entre 0 et n − 1.
Par exemple T : entier[10] défini un tableau de 10
variables entières T[0], ..., T[9].
K Musumbu Composition d’Algorithmes
Structure de données
Un tableau T : type[n]
est une structure de données qui contient n variables de
même type, chacune accessible par un indice compris
entre 0 et n − 1.
Par exemple T : entier[10] défini un tableau de 10
variables entières T[0], ..., T[9].
K Musumbu Composition d’Algorithmes
Séquence
Algorithme .1 : ComplexiteSequenceInstructions()
]cal,ecr = 4 donc Ω(1), O(1) donc Θ(1)
Lecture1;
Lecture2;
Calcul3; /* 1 */
Ecriture4; /* 1 */
Lecture5;
Calcul6; /* 1 */
Ecriture7; /* 1 */
Algorithme .2 : ComplexiteSequence()
Ω(max(f1 (n), f2 (n), f3 (n))), O(max(g1 (n), g2 (n), g3 (n)))
< S1 >; /* Complexité de S1 : Ω(f1 (n)), O(g1 (n)) */
< S2 >; /* Complexité de S2 : Ω(f2 (n)), O(g2 (n)) */
< S3 >; /* Complexité de S3 : Ω(f3 (n)), O(g3 (n)) */
K Musumbu Composition d’Algorithmes
Boucle “pour”
Algorithme .3 : ComplexiteBouclePourInstructions(T)
Données : T, un tableau de n entiers
]cal,ecr = 2n + 3 donc Ω(n), O(n) donc Θ(n)
n ← longueur(T); /* 1 */
somme ← 0; /* 1 */
pour i=0 à n-1 faire /* 2n */
somme ← somme+T[i]; /* calcul + écriture : 2
*/
retourner somme; /* 1 */
Algorithme .4 : ComplexiteBouclePour(T)
Données : T, un tableau de n entiers
Ω(n f (n)), O(n g(n))
n ← longueur(T); /* Θ(1) */
pour i=0 à n-1 faire /* Ω(n × f (n)), O(n × g(n)) */
< S(T [i]) > ; /* Complexité de S : Ω(f (n)), O(g(n))
*/ K Musumbu Composition d’Algorithmes
Boucle “tant que” et “répéter”
Algorithme .5 : ComplexiteBoucleWhileInstructions(T,X)
Données : T, un tableau de n entiers, X un entier
]cal,ecr = [7..3n + 5] donc Ω(1), O(n)
n ← longueur(T); /* 1 */
i ← 0; /* 1 */
[Link] trouve ← Faux; /* 1 */
tant que non trouve et i<n faire /* [3..3n + 1] */
trouve ← X=T[i]; /* 1 */
i ← i+1; /* 1 */
retourner trouve; /* 1 */
K Musumbu Composition d’Algorithmes
Boucle “tant que” et “répéter”
Algorithme .6 : ComplexiteBoucleWhileSimple(T,X)
Données : T, un tableau de n entiers, X un entier
Ω(f (n)), O(n g(n))
n ← longueur(T); /* Θ(1) */
i ← 0; /* Θ(1) */
trouve ← Faux; /* Θ(1) */
tant que non trouve et i<n faire
/* [1 + f (n)..1 + n × (g(n) + 2)] */
trouve ← < S(T [i]) > ; /* Complexité de S :
Ω(f (n)), O(g(n)) */
i ← i+1; /* Θ(1) */
retourner trouve; /* Θ(1) */
K Musumbu Composition d’Algorithmes
Boucle “tant que” et “répéter”
Algorithme .7 : ComplexiteBoucleWhile(D)
Données : une donnée de taille n
Ω(f (n)), O(?)
P ← Vrai; /* Θ(1) */
tant que P faire
P ← < S(D) > ; /* Complexité de S :
Ω(f (n)), O(g(n)) */
retourner P; /* Θ(1) */
K Musumbu Composition d’Algorithmes
Boucles imbriquées
Il suffit d’appliquer les formules précédentes en substituant
<S> par une boucle. Cela donne naturellement :
2 boucles “pour” simples imbriquées : Θ(n × m) ou bien
Θ(n2 ) si n = m. On parle de complexité “quadratique”.
k boucles “pour” simples imbriquées : Θ( ki ni ) ou bien
Q
Θ(nk ).
2 boucles “tant que” simples imbriquées : Ω(1), O(n m) ou
bien Ω(1), O(n2 ) si n = m.
...
K Musumbu Composition d’Algorithmes
Boucles imbriquées
Il suffit d’appliquer les formules précédentes en substituant
<S> par une boucle. Cela donne naturellement :
2 boucles “pour” simples imbriquées : Θ(n × m) ou bien
Θ(n2 ) si n = m. On parle de complexité “quadratique”.
k boucles “pour” simples imbriquées : Θ( ki ni ) ou bien
Q
Θ(nk ).
2 boucles “tant que” simples imbriquées : Ω(1), O(n m) ou
bien Ω(1), O(n2 ) si n = m.
...
K Musumbu Composition d’Algorithmes
Boucles imbriquées
Il suffit d’appliquer les formules précédentes en substituant
<S> par une boucle. Cela donne naturellement :
2 boucles “pour” simples imbriquées : Θ(n × m) ou bien
Θ(n2 ) si n = m. On parle de complexité “quadratique”.
k boucles “pour” simples imbriquées : Θ( ki ni ) ou bien
Q
Θ(nk ).
2 boucles “tant que” simples imbriquées : Ω(1), O(n m) ou
bien Ω(1), O(n2 ) si n = m.
...
K Musumbu Composition d’Algorithmes
Boucles imbriquées
Il suffit d’appliquer les formules précédentes en substituant
<S> par une boucle. Cela donne naturellement :
2 boucles “pour” simples imbriquées : Θ(n × m) ou bien
Θ(n2 ) si n = m. On parle de complexité “quadratique”.
k boucles “pour” simples imbriquées : Θ( ki ni ) ou bien
Q
Θ(nk ).
2 boucles “tant que” simples imbriquées : Ω(1), O(n m) ou
bien Ω(1), O(n2 ) si n = m.
...
K Musumbu Composition d’Algorithmes
Branchement
Algorithme .8 : ComplexiteBranchement(P)
Données : P un predicat, n taille des données
Ω(min(f1 (n), f2 (n)), O(max(g1 (n), g2 (n)))
si P alors
< S1 > ; /* Complexité de S1 : Ω(f1 (n)), O(g1 (n))
*/
sinon
< S2 > ; /* Complexité de S2 : Ω(f2 (n)), O(g2 (n))
*/
K Musumbu Composition d’Algorithmes
Composition
Il suffit de remarquer que les deux algorithmes suivants
s’exécutent de la même façon.
Algorithme .9 : Maximum3(X,Y,Z)
Données : 3 entiers X, Y et Z
Résultat : Le plus grand des trois
retourner Maximum2(Maximum2(X,Y)Z);
Algorithme .10 : Maximum3Equiv(X,Y,Z)
Données : 3 entiers X, Y et Z
Résultat : Le plus grand des trois
Θ(1)
aux ← Maximum2(X,Y);
retourner Maximum2(aux,Z);
Algorithme .11 : ComplexiteComposition(X)
Données : Une donnée X de taille n
O(max(g2(n),
Ω(max(f 2(n), f 1(aux))),K Musumbu g1(aux)))
Composition d’Algorithmes
Compromis entre temps et espace
Algorithme .13 : ElementPlusFrequentV1(T)
Données : Un tableau T d’entiers naturels
Résultat : La valeur la plus fréquente, et son nombre
d’occurrences
Θ(n2 ) en temps, Θ(1) en espace
n ← longueur(T);
si n>0 alors /* Θ(n2 ) */
nbMax ← 0;
pour i=0 à n-1 faire /* Θ(n2 ) */
cpt ← 0;
pour j=0 à n-1 faire /* Θ(n) */
si T[i]=T[j] alors /* Θ(1) */
cpt ← cpt+1;
si cpt>nbMax alors /* Θ(1) */
nbMax ← cpt;
eltMax ← T[i];
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Techniques d’évaluation de la complexité
Deux techniques principales :
Appliquer pour chaque structure de contrôle les résultats
de complexité, en commençant par les structures les plus
imbriquées.
Relations de récurrences :
T (n + 1) = T (n), complexité constante en 1.
T (b × n) = T (n) + c, (avec c > 0), complexité
logarithmique en logb (n) ≡ log2 (n) ≡ ln(n).
T (n + 1) = T (n) + c, (avec c > 0), complexité linéaire en n.
T (n + 1) = T (n) + ak nk + ak −1 nk −1 + · · · + a0 , (avec
ak > 0), complexité polynomiale en nk +1 .
T (n + 1) = c × T (n), (avec c > 0), complexité exponentielle
cn.
T (n + 1) = (n + 1) × T (n), complexité factorielle n!.
Attention aux Retourner en milieu de boucle, qui rendent
plus difficile le calcul de la complexité.
K Musumbu Composition d’Algorithmes
Pile d’exécution et passages de paramètres
Contenu et rôle d’une pile d’exécution
Pour l’algorithme appelé :
le nom de l’algorithme.
la valeur du compteur ordinal correspondant au “début de
programme”.
la liste des valeurs des variables passées en paramètres.
K Musumbu Composition d’Algorithmes
Pile d’exécution et passages de paramètres
Contenu et rôle d’une pile d’exécution
Pour l’algorithme appelé :
le nom de l’algorithme.
la valeur du compteur ordinal correspondant au “début de
programme”.
la liste des valeurs des variables passées en paramètres.
K Musumbu Composition d’Algorithmes
Pile d’exécution et passages de paramètres
Contenu et rôle d’une pile d’exécution
Pour l’algorithme appelé :
le nom de l’algorithme.
la valeur du compteur ordinal correspondant au “début de
programme”.
la liste des valeurs des variables passées en paramètres.
K Musumbu Composition d’Algorithmes
Pile d’exécution et passages de paramètres
Contenu et rôle d’une pile d’exécution
Pour l’algorithme appelé :
le nom de l’algorithme.
la valeur du compteur ordinal correspondant au “début de
programme”.
la liste des valeurs des variables passées en paramètres.
K Musumbu Composition d’Algorithmes
Exemple
Algorithme .17 : EvolutionPileExecution()
Données : Une liste de prédicats
Résultat : La branche exécutée
v1 ← . . . ;
v2 ← . . . ;
v3 ← Algorithme(v1);
v4 ← . . . ;
v2 ← . . . ;
v4 ← Algorithme(v2);
v2 ← . . . ;
v3 ← Algorithme(v2);
K Musumbu Composition d’Algorithmes
