I. Programme et algorithme

En programmation, on parle souvent d'algorithme. C'est une sorte de programme abstrait, qui décrit une méthode pour résoudre un problème, indépendamment de tout langage de programmation. Par exemple :

Une implémentation d'un algorithme est une traduction de l'algorithme dans un langage de programmation. Cela peut impliquer une réflexion et des choix supplémentaires.

def recherche_lineaire(L, x):
    """Cherche un élément x dans une liste L. Renvoie True si l'élément est présent, False sinon."""
    for y in L:
        if x == y:
            return True
    return False

Exemples d'utilisation :

def recherche_lineaire(L, x):
    """Cherche un élément x dans une liste L. Renvoie True si l'élément est présent, False sinon."""
    for y in L:
        if x == y:
            return True
    return False

print(recherche_lineaire([3, 1, 4, 1, 5], 4))
print(recherche_lineaire([3, 1, 4, 1, 5], 2))
print(recherche_lineaire([], 2))

II. Complexité d'un algorithme

a) Opérations élémentaires

La complexité d'un algorithme est une estimation du temps qu'il faut pour qu'il s'exécute.

On va compter les opérations élémentaires dans un programme ou un algorithme. Par exemple, dans l'algorithme de recherche linéaire ci-dessus, on fait une comparaison x = y pour chaque élément de la liste. Mais est-ce qu'on compte la boucle elle-même ? Et les retours ?

En réalité, toutes les opérations élémentaires ne prennent pas le même temps à s'exécuter. Voici un ordre de grandeur du nombre de cycles du processeur nécessaires à chacune :

Cela n'a donc pas vraiment de sens de compter toutes les opérations une par une.

b) Complexité asymptotique

On va seulement prendre l'ordre de grandeur du nombre d'opérations élémentaires, en fonction de la taille de l'entrée (en général nommée ).

On utilise la notation , pour dire "au plus de l'ordre de ...". On peut avoir par exemple :

• : le nombre d'opérations ne dépend pas de la taille de l'entrée ;
• : le nombre d'opérations est proportionnel à la taille de l'entrée ;
• : le nombre d'opérations est proportionnel au carré de la taille de l'entrée ;
• ...

c) Calculer la complexité d'un algorithme

Dans votre cas :

1. Sauf exception, toutes les opérations et fonctions fournies sont en temps constant, soit .
2. Cas des boucles : si une boucle fait itérations, et que chaque itération est, dans le pire cas, en , alors le total est en .

Par exemple, pour la recherche linéaire :

def recherche_lineaire(L, x):
    """Cherche un élément x dans une liste L. Renvoie True si l'élément est présent, False sinon."""
    for y in L:
        if x == y:
            return True
    return False

On a len(L) itérations de la boucle, et chaque itération est en . Donc la complexité est en au total.

def indice_max(L):
    """Renvoie l'indice de l'élément maximal de L"""
    i_max = 0
    val_max = L[0]
    for i in range(1, len(L)):
        if L[i] > val_max:
            val_max = L[i]
            i_max = i
    return i_max

Vous pouvez tester la fonction ici :

def indice_max(L):
    """Renvoie l'indice de l'élément maximal de L"""
    i_max = 0
    val_max = L[0]
    for i in range(1, len(L)):
        if L[i] > val_max:
            val_max = L[i]
            i_max = i
    return i_max

indice_max([3, 1, 4, 1, 5, 9, 2, 6])

La fonction tracer_variables (du module affichage du site) exécute une fonction et affiche les valeurs de ses variables au début, à la fin de chaque tour de boucle, et à la fin :

d) Mesurer le temps d'exécution

On peut vérifier expérimentalement la complexité d'une fonction, en mesurant son temps d'exécution pour des entrées de plus en plus grandes. Comparons la recherche linéaire, en , avec une fonction qui cherche si une liste contient deux fois le même élément, en comparant tous les couples d'éléments, en :

La courbe de la recherche linéaire est (à peu près) une droite, celle de contient_doublon une parabole : quand la taille double, le temps est multiplié par 4.

Exercices

def nb_paires_egales(L):
    c = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            if L[i] == L[j]:
                c += 1
    return c

def nb_occurrences(L, x):
    c = 0
    for y in L:
        if y == x:
            c += 1
    return c

def deux_plus_grands(L):
    a, b = max(L[0], L[1]), min(L[0], L[1])   # a >= b
    for x in L[2:]:
        if x > a:
            a, b = x, a
        elif x > b:
            b = x
    return a, b