Analyse de la complexite algorithmique.pdf

(55 KB) Pobierz
Analyse de la complexité algorithmique (1)
L’analyse de la complexité telle que nous
l’avons vue jusqu’à présent nous a essentiellement
servi à déterminer si un problème est ou non facile
(i.e. soluble par un algorithme de complexité polynomiale).
Cependant, lorsqu’on s’intéresse à des problèmes polynomiaux
(et c’est majoritairement le cas en informatique classique), il peut souvent
y avoir
plusieurs algorithmes polynomiaux
pour résoudre
un problème donné.
Dans ce cas, il faut faire une analyse plus fine
de leur complexité algorithmique, de façon à
pouvoir choisir
le plus performant.
Informatique II
Algorithmique
– 53 –
Analyse de la complexité algorithmique (2)
Comme la résolution algorithmique elle-même,
l’analyse de complexité des algorithmes
est une
tâche difficile
pour laquelle il n’existe malheureusement
pas de recette générale.
Pour cette raison, nous allons tout d’abord étudier deux exemples
concrets qui nous servirons à illustrer quelques «trucs
et astuces»
Informatique II
Algorithmique
– 54 –
Analyse de la complexité: exemple (1)
Cas de la recherche d’un élément dans une liste triée
Soit l’algorithme naïf suivant :
appartient1(x,E) {
for (i=0; i<taille(E); i++) { if (x==E[i]) return (true); }
return (false);
}
et l’algorithme de recherche par dichotomie déjà vu (légèrement reformulé ici):
appartient2(x,E) { dichotomie(x,E,0,taille(E)); }
dichotomie(x,E,i,j) {
if (i>j) return(false);
else {
k = (i+j)/2; u = E[k];
if (x==u) return(true);
else {
if (x<u) return(dichotomie(x,E,i,k-1);
else return(dichotomie(x,E,k+1,j);
} } }
Informatique II
Algorithmique
– 55 –
Analyse de la complexité: exemple (2)
Pour calculer l’ordre de grandeur
de la complexité algorithmique d’algorithmes spécifiques,
plusieurs simplifications peuvent être faites
:
1.
Mesure de la taille des entrées:
pour une entrée constituée de
m
données d’entrée, la taille à prendre dans l’approche
théorique est la taille de la séquence binaire permettant de coder ces m données
d’entrée. Cette taille étant dans la plupart des cas de la forme
m·A+B
où A et B sont des
constantes, on pourra
utiliser m comme mesure de la taille des entrées,
et donc
exprimer la complexité par rapport à
m
(en effet O((m·A+B)
k
) = O(m
k
)).
2.
Mesure de la complexité temporelle
:
Dans l’approche théorique, la complexité temporelle est mesurée par le nombre de
déplacements effectués par le tête de lecture/écriture lors d’exécution d’une machine de
Turing représentant l’algorithme. Dans la pratique, cette machine de Turing est
rarement disponible... et l’on mesure la complexité par le
nombre d’instructions
élémentaires nécessaires à l’exécution de l’algorithme.
Informatique II
Algorithmique
– 56 –
Analyse de la complexité: exemple (3)
Par
instruction élémentaire,
nous entendrons ici
toute instruction qui peut être réalisée par une machine de Turing
en un nombre constant de déplacements de la tête de lecture/écriture.
Exemples d’instructions élémentaires:
• écrire un caractère à l’écran;
• lire un caractère dans un fichier;
• affecter une valeur atomique (un caractère, un entier, un réel, ...) à une variable
(attention: l’affectation d’une valeur composée peut ne pas correspondre à un nombre constant
de déplacements en cas dépendance par rapport au nombre d’éléments constituant la valeur
composée);
• réaliser une opération arithmétique sur des valeurs atomiques;
• ...
Informatique II
Algorithmique
– 57 –

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin