Compter des opérations élémentaires.☘

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.

On commence donc ici à compter quelques opérations pour débuter la réflexion sur ce problème important de la "complexité" d'un programme.

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

Exercice 1☘

Reprenons le programme de recherche du maximum:

def elementMax(liste):
    """
    liste -- liste d'entiers

    renvoie la valeur du plus grand élément contenu dans liste.
    """
    pge = liste[0] # pge sera le plus grand élément
    for element in liste:
        if element > pge: pge = element
    return pge

Quel est le nombre de comparaisons effectuées lors d'un appel de la fonction?

Réponse

Notons n le nombre d'éléments de la liste passée en argument de la fonction. Il y a une comparaison (if element > pge) à chaque passage dans la boucle for. Il y a donc exactement n comparaisons.

Exercice 2☘

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

def estPresent(tab, valeur):
    """
    tab -- liste d'entiers
    valeur -- entier

    renvoie True si valeur est élément de tab, False sinon
    >>> estPresent([], 3)
    False
    >>> estPresent([2,6], 3)
    False
    >>> estPresent([3,2,6], 3)
    True
    """
    for element in tab:
        if element == valeur: return True
    return False

Quel est le nombre de comparaisons effectuées lors d'un appel de la fonction?

Réponse

Notons n le nombre d'éléments de la liste passée en argument.

L'élément peut être trouvé au premier test (cas tab[0] = valeur), et il n'y aura dans ce cas qu'un seul test de comparaison.
L'élément peut être trouvé au second test (cas tab[1] = valeur), et il y aura eu dans ce cas deux tests de comparaison.
...
L'élément peut être trouvé au dernier test (cas tab[-1] = valeur), et il y aura eu dans ce cas n tests de comparaison.
L'élément peut également être absent: n tests également.

Le nombre de comparaisons peut donc être n'importe quel entier entre 0 et n (0 est le cas où la liste passée en argument est une liste vide).

Commentaire☘

La situation est donc un peu différente pour nos deux fonctions:

dans le cas de la recherche d'un extremum, le nombre d'opérations est toujours égal à la longueur de liste.
dans le cas de la recherche de présence d'un élément, ce nombre varie suivant les entrées.

Dans une situation comme le cas 2, on s'intéressera souvent au nombre d'opérations "au pire" et au nombre d'opérations "au mieux", ou 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?

Un algorithme plutôt mauvais en termes de nombre d'opérations dans le cas au pire peut parfois être tout de même intéressant si l'on sait que toutes les entrées que nous utiliserons relèvent en fait des entrées correspondant au cas "au mieux".

On cherche aussi parfois à estimer le nombre d'opérations moyen sur les entrées. Il peut arriver que l'on sache que l'algorithme utilisé sera mauvais pour quelques entrées, mais que cela soit tout de même acceptable si, en moyenne sur l'ensemble des entrées utilisées, le nombre d'opérations est "correct".

Nombre d'opérations 'correct'

On parle ci-dessus de nombre d'opérations correct. Sans définir précisément cette notion, il s'agit d'être certain que l'algorithme s'exécutera en un temps raisonnable.

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!

On voit avec ces exemples que cette notion de "correct" est une notion relative aux objectifs, au rôle du programme.

On essaie aussi, en théorie de la complexité, de déterminer la "nature" de la fonction exprimant la complexité d'un algorithme (polynôme, exponentielle...): une croissance exponentielle étant beaucoup plus rapide qu'une croissance polynomiale (sur les "grandes" valeurs), cette classification permet d'avoir une première partition des algorithmes (qui joue un rôle théorique important).

Nombre affine d'opérations☘

Si les comptes pour nos deux programmes différent dans le détail, 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 liste (ici la fonction affine est tout simplement n $\mapsto$ n). On parlera de complexité linéaire.

Une telle situation est toujours meilleure qu'un algorithme qui demanderait n² opérations. Nous y reviendrons.