Previous Up Next

Annexe A  Le coût d’un algorithme

Ce chapitre rappelle les différents moyens d’évaluer le coût d’un algorithme.

A.1  Une définition très informelle des algorithmes

La formalisation de la notion d’algorithme est assez tardive. Les travaux fondamentaux de Post et de Turing datent de la fin des années 30. Nous ne disposons pas, pour ce cours, des outils qui permettent d’exposer très rigoureusement la notion d’algorithme et de complexité algorithmique. Nous nous contenterons de la définition suivante : Un algorithme est un assemblage ordonné d’instruction élémentaires qui à partir d’un état initial bien spécifié permettent d’aboutir à un état final, lui aussi bien spécifié. Notons que pour qu’un algorithme puisse s’exécuter, les données (d’entrées, de sortie et intermédiaires) sont structurées. Ceci permet de les conserver, de les utiliser et de les modifier.

Les étapes élémentaires sont éventuellement répétées (notion de boucle) et sont soumises à des test logiques (instruction de contrôle). Les algorithmes peuvent, la plupart du temps, être codés à l’aide de programmes informatique

A.2  Des algorithmes “efficaces” ?

Qu’est-ce qu’un bon algorithme ? C’est bien entendu un algorithme qui répond correctement au problème posé. On souhaite généralement qu’il soit aussi rapide et n’utilise pas trop de mémoire.

Quel que soit la mesure choisie, il est clair que la qualité de l’algorithme n’est pas absolue mais dépend des données d’entrée. Les mesures d’efficacité sont donc des fonctions des données d’entrée. Pour évaluer le temps d’exécution d’un algorithme (par exemple un tri) sur une donnée d (par exemple un ensemble d’entiers à trier), on calcule le nombre d’opérations élémentaires (opérations arithmétiques, affectation, instruction de contrôle, etc.) effectuées pour traiter la donnée d. On admet communément que toute opération élémentaire prend un temps constant. Attention, cette hypothèse n’est valable que si tous les nombres sont codés sur un même nombre de bits.

Plutôt que de calculer le nombre d’opérations associé à chaque donnée, on cherche souvent à évaluer le nombre d’opérations nécessaires pour traiter les données qui ont une certaine “taille”. Il existe souvent un paramètre naturel qui est un estimateur raisonnable de la taille d’une donnée (par exemple, le nombre n d’éléments à trier pour un algorithme de tri, la taille n,m d’une matrice pour le calcul du déterminant, la longueur n d’une liste pour une inversion, etc.). Pour simplifier nous supposerons dans la suite que la “taille” d’une donnée est évaluée par un unique entier n.

Les informaticiens s’intéressent à l’ordre de grandeur des temps d’exécution (ou de taille mémoire) quand n devient très grand. Le coût exact en secondes est en effet très difficile à mesurer et dépend de très nombreux paramètres (cf. Section A.4). On utilise donc les notations O, Θ et Ω pour exprimer des relations de domination : Soient f et g deux fonctions définies des entiers naturels vers les entiers naturels.

Dans la pratique, le temps d’exécution d’un algorithme dépend non seulement de n mais aussi de la structure des données. Par exemple, le tri d’une liste d’entiers est, pour certains algorithmes, plus rapide si la liste est partiellement triée plutôt que dans un ordre parfaitement aléatoire. Pour analyser finement un algorithme, on a donc besoin de plusieurs mesures :

Ces notions s’étendent à la consommation mémoire d’un algorithme. On parle alors de complexité spatiale (maximale ou moyenne).

En pratique, le pire cas est rarement atteint et l’analyse en moyenne semble plus séduisante. Attention tout de même à deux écueils pour les calculs en moyenne :

A.3  Quelques exemples

Nous donnons ici des exemples simples et variés d’analyse d’algorithmes. De nombreux autres exemples sont dans le polycopié.

A.3.1  Factorielle

La première version de notre programme permettant de calculer n! est itérative.

        int f = 1;
        for (int i= 2; i <= n; i++)
            f = f * i;
        return f;
    }

Nous avons n−1 itérations au sein desquelles le nombre d’opérations élémentaires est constant. La complexité est O(n)

La seconde version est récursive. Soit C(n) le nombre d’opérations nécessaires pour calculer factorielle(n). Nous avons alors C(n) ≤ λ + C(n−1) où λ est une constante qui majore le nombre d’opérations précédent l’appel récursif. De plus C(1) se calcule en temps constant et donc C(n) = O(n).

    if (n <= 0)
       return 1;
    else
       return n * factorielle(n-1);
  }

A.3.2  Recherche Dichotomique

Considérons un tableau T de n entiers triés. On cherche à tester si un entier v donné se trouve dans le tableau. Pour ce faire, on utilise une recherche “dichotomique”.

    static boolean trouve(int[] T, int v, int min, int max){
        if(min >= max) // vide
            return false;
        int mid = (min + max) / 2;
        if (T[mid] == v)
            return true;
        else if (T[mid] > v)
            return trouve(T, v, min, mid);
        else
            return trouve(T, v, mid + 1, max);
    }

La fonction trouve cherche l’entier v dans T entre les indices min et max -1. Pour effectuer une recherche sur tout le tableau, il suffit d’appeler trouve(T, v, 0, T.length).

Le nombre total d’opérations est proportionnel au nombre de comparaisons C(n) effectuées par l’algorithme récursif. Et donc, nous avons immédiatement : C(n) = 1 + C(n/2). Soit donc, C(n) = O(logn).

A.3.3  Tours de Hanoi

Le très classique problème des “tours de Hanoi” consiste à déplacer des disques de diamètres différents d’une tour de départ à une tour d’arrivée en passant par une tour intermédiaire. Les règles suivantes doivent être respectées : on ne peut déplacer qu’une disque à la fois, et on ne peut placer un disque que sur un disque plus grand ou sur un emplacement vide.

Identifions les tours par un entier. Pour résoudre ce problème, il suffit de remarquer que si l’on sait déplacer une tour de taille n de la tour ini vers dest, alors pour déplacer une tour de taille n+1 de ini vers dest, il suffit de déplacer une tour de taille n de ini vers temp, un disque de ini versdest et finalement la tour de hauteur n detemp versdest.

    if (n == 1){ // on sait le faire
        System.out.println("deplace" + ini + " " + dest);
        return;
    }            // sinon recursion
    hanoi(n - 1, ini, dest, temp);
    System.out.println("deplace" + ini + " " + dest);
    hanoi(n-1, temp, ini, dest);
}

Notons C(n) le nombre d’instructions élémentaires pour calculer hanoi(n, ini, temp, dest). Nous avons alors C(n+1) ≤ 2 C(n) + λ, où λ est une constante. Tour de Hanoi est exponentielle.

A.3.4  Recherche d’un nombre dans un tableau, complexité en moyenne

On suppose que les éléments d’un tableau T de taille n sont des nombres entiers distribués de façon équiprobable entre 1 et k (une constante). Considérons maintenant l’algorithme de recherche ci-dessous qui cherche une valeur v dans T.

        for (int i = 0; i < T.length; i++)
            if (T[i] == v)
                return true;
        return false;
    }

La complexité dans le pire cas est clairement O(n). Quelle est la complexité en moyenne ?

Remarquons que nous avons kn tableaux. Parmi ceux-ci, (k−1)n ne contiennent pas v et dans ce cas, l’algorithme procède à exactement n itérations. Dans le cas contraire, l’entier est dans le tableau et sa première occurrence est alors i avec une probabilité de

(k−1)i−1
ki

et il faut alors procéder à i itérations. Au total, nous avons une complexité moyenne de

C = 
(k−1)n
kn
 × n + 
n
i = 1
 
(k−1)i−1
ki
 × i

Or

∀ x
n
i = 1
 i xi−1 = 
1 +xn(nx −n−1)
(1−x)2

(il suffit pour établir ce résultat de dériver l’identité ∑i = 1n xi = 1 − xn+1/1−x) et donc

C =  n 
(k−1)n
kn
 + k 


1 − 
(k−1)n
kn
(1 + 
n
k
)


k 





1 − 


1−
1
k



n



 






A.4  Coût estimé vs. coût réel

Les mesures présentées dans ce chapitre ne sont que des estimations asymptotique des algorithmes. En pratique, il faut parfois atteindre de très grandes valeurs de n pour qu’un algorithme en O(n logn) se comporte mieux qu’un algorithme quadratique.

Les analyses de complexité peuvent servir à comparer des algorithmes mais le modèle de coût est relativement simple (par exemple, les opérations d’accès aux disques, ou le trafic réseau généré ne sont pas pris en compte alors que ces paramètres peuvent avoir une influence considérable sur un programme). Il est toujours nécessaire de procéder à des analyses expérimentales avant de choisir le “meilleur” algorithme, i.e., l’algorithme spécifiquement adapté au problème que l’on cherche à résoudre.


Previous Up Next