Compter des opérations élémentaires

Avec cette partie, nous allons commencer à réfléchir sur la « complexité » d'un programme.

En effet, le temps d'exécution d'un programme dépend du nombre d'opérations élémentaires effectuées lors de l'exécution de programme.

Pour simplifier la tâche, on se limitera dans cette partie à compter un seul type d'opérations élémentaires : les comparaisons (c'est-à-dire les tests utilisant <, <=, >, >=, ==, !=).

Exemple n°1

Reprenons le programme de recherche du maximum :

def valeur_max(tab):
    """
    tab - list, tableau non vide de nombres (entiers ou flottants)    
    Sortie: nombre (int ou float) - valeur du plus grand élément contenu dans tab
    """
    pge = tab[0]            # pge sera le plus grand élément
    for element in tab:
        if element > pge:
            pge = element
    return pge

Quel est le nombre de comparaisons effectuées lors d'un appel valeur_max(tab), où tab est un tableau quelconque ayant n éléments ?

Réponse

Le tableau passé en argument de la fonction comporte n éléments donc il y a n passages dans la boucle for.
A chaque passage dans cette boucle, il y a une comparaison (if element > pge).
Il y a donc exactement n comparaisons lors d'un appel à la fonction valeur_max().

Exemple n°2

Reprenons maintenant la fonction recherchant la présence d'un élément :

def est_present(tab, valeur):
    """
    tab - list, tableau d'entiers
    valeur - entier    
    Sortie: bool - True si valeur est un élément de tab, False sinon
    """
    indice = 0
    dernier_indice = len(tab)-1
    while (indice <= dernier_indice) and (tab[indice] != valeur):
        indice = indice + 1
    if indice == dernier_indice+1:
        return False
    else:
        return True

Quel est le nombre de comparaisons effectuées lors d'un appel de la fonction ?
On considère à nouveau que tab est un tableau quelconque ayant n éléments.

Réponse

n est le nombre d'éléments du tableau passé en argument.
A chaque tour de la boucle « while », deux tests sont effectués : indice <= dernier_indice et tab[indice] != valeur.

• L'élément peut être trouvé au premier tour (cas tab[0] = valeur).
  Dans ce cas, il y a deux tests de comparaison.
• L'élément peut être trouvé au second tour (cas tab[1] = valeur).
  Dans ce cas, il y a quatre tests de comparaison.
• ...
• L'élément peut être trouvé au dernier tour (cas tab[dernier_indice] = valeur).
  Dans ce cas, il y a 2*n tests de comparaison.
• L'élément peut également être absent : 2*n tests également.

Il reste enfin un dernier test pour vérifier si le dernier élément est celui cherché ou non.

Le nombre de comparaisons peut donc être n'importe quel entier entre 1 et 2 n+1 (1 est le cas où le tableau passé en argument est un tableau vide).

Commentaire

La situation est donc un peu différente pour nos deux fonctions (pour nos deux types d'algorithmes) :

• dans le cas du parcours complet d'un tableau afin d'en rechercher le maximum, le nombre d'opérations est toujours égal à la longueur du tableau.

• dans le cas de la recherche de présence d'un élément, ce nombre d'opérations varie suivant les entrées.

Nombre d'opérations

Dans une situation comme l'exemple n°2, on s'intéressera souvent au nombre d'opérations « dans le pire des cas » et au nombre d'opérations « dans le meilleur des cas ». En d'autres termes :

• quelles sont les entrées donnant lieu au plus petit nombre d'opérations élémentaires lors de l'exécution de la fonction ?

• quelles sont les entrées donnant lieu au plus grand nombre d'opérations élémentaires lors de l'exécution de la fonction ?

Attention

Un algorithme plutôt mauvais en termes de nombre d'opérations dans le cas « au pire » peut parfois se montrer intéressant si l'on sait que toutes les entrées qui seront utilisées relèvent en fait du cas « au mieux » .

Nombre d'opérations acceptable

Parfois, on cherchera à estimer le nombre moyen d'opérations sur les entrées.
En effet, il peut arriver que l'on sache que l'algorithme utilisé sera mauvais pour quelques entrées, mais qu'en moyenne (sur l'ensemble des entrées utilisées), le nombre d'opérations est « correct », c'est-à-dire acceptable.

Cette notion de nombre d'opérations « correct » est relative aux objectifs, au rôle du programme à réaliser : il s'agit d'être certain que l'algorithme s'exécutera en un temps raisonnable.
Par exemple :

• Si un algorithme de pilotage d'un avion ne finit ses calculs qu'après le crash de l'avion : le nombre d'opérations n'était pas correct !
• De la même façon, si des calculs rendent l'exécution d'un jeu non fluide, l'échec commercial du jeu est garanti : le nombre d'opérations n'était pas correct !

Nombre d'opérations affine

Dans les exemples n°1 et n°2, les décomptes du nombre de comparaisons sont différents lorsqu'on les détaille.
Toutefois, on peut tout de même assurer dans les deux cas que le nombre de comparaisons est majoré par une fonction affine de la longueur de tableau. Ici, la fonction affine est n $\mapsto$ 2*n+1 pour tout entier naturel n.

Lorsqu'un nombre d'opération est majoré par une fonction affine, on parle de complexité linéaire.

Une telle situation est toujours meilleure qu'un algorithme qui demanderait n² opérations. Nous y reviendrons plus tard dans l'année...