C17.2 : Complexité d'un algorithme

Présentation

Préambule

Lorsqu'on écrit un algorithme, trois questions fondamentales se posent :

  • • Est-ce qu'il se termine ? => C'est ce que l'on appelle la terminaison.
  • • Est-ce qu'il donne le résultats attendu ? => C'est ce que l'on appelle la correction.
  • • Est-ce qu'il donne le résultat en utilisant des ressources (temps, mémoire...) raisonnables ? => C'est ce que l'on appel la complexité ou le coût.

Dans cette activité, nous allons parler de la complexité (que l'on appelle aussi le coût) d'un algorithme.

Définition

La complexité (le coût) d'un algorithme est le nombre d'opérations élémentaires effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille des données traitées par l'algorithme.

Application à quelques algorithmes classiques avec des listes

Somme des valeurs d'une liste

🖥️ 1) Écrire une fonction qui prend une liste d'entiers en paramètre et renvoie la somme des valeurs de la liste.

🖊️ 2) Déterminer la complexité (le coût) de cet algorithme, c'est-à-dire, ici, le nombre d'additions que l'algorithme effectue en fonction de la longueur \(n\) de la liste.

🖥️ 3) Ajouter un compteur à la fonction de façon à pouvoir afficher en fin de fonction le nombre de boucles effectué par le programme.

Afficher la correction

1) Fonction

def somme_liste(L):
    s = 0
    for elt in L:
        s = s + elt
    return s

2) Coût

A chaque boucle, le programme exécute 1 addition (ligne 4).

Or le programme exécute la boucle autant de fois qu'il y a d'éléments dans la liste, c'est-à-dire \(n\) fois.

Donc la complexité (le coût) est égale à \(n\).

3) Compteur

def somme_liste(L):
    compteur = 0
    s = 0
    for elt in L:
        s = s + elt
        compteur = compteur + 1
    print(compteur)
    return s

Recherche de la valeur minimale d'une liste

🖥️ 1) Écrire une fonction qui prend une liste d'entiers (non vide) en paramètre et renvoie la plus petite valeurs de la liste.

🖊️ 2) Déterminer la complexité (le coût) de cet algorithme, c'est-à-dire, ici, le nombre de comparaisons que l'algorithme effectue en fonction de la longueur \(n\) de la liste.

🖥️ 3) Ajouter un compteur à la fonction de façon à pouvoir afficher en fin de fonction le nombre de boucles effectué par le programme.

Afficher la correction

1) Fonction

def somme_liste(L):
    val_min = L[0]
    for val in L:
        if val < val_min:
            val_min = val
    return val_min

2) Coût

A chaque boucle, le programme exécute 1 comparaison (ligne 4).

Or le programme exécute la boucle autant de fois qu'il y a d'éléments dans la liste, c'est-à-dire \(n\) fois.

Donc la complexité (le coût) est égale à n.

3) Fonction

def somme_liste(L):
    compteur = 0
    val_min = L[0]
    for val in L:
        compteur = compteur + 1
        if val < val_min:
            val_min = val
    print(compteur)
    return val_min

Vocabulaire

Lorsque la complexité (le coût) est proportionnelle à la taille des données, on dit que la complexité est linéaire.

Application aux algorithmes de recherche dans une liste triée

Dans cette partie, on s'intéresse aux algorithmes de recherche dans une liste triée.

On assimilera le coût de l'algorithme au nombre d'itérations effectuées par la boucle.

La taille des données sera la longueur de la liste et pourra être notée \(n\).

On souhaite donc savoir combien l'algorithme doit faire de boucle en fonction de la longueur de la liste dans laquelle on recherche l'élément.

Complexité pour la recherche séquentielle

Reprendre la fonction recherche_seq_triee(E, L) de l'activité précédente.

🖊️ 1) Pour quelles valeurs recherchées le nombre de comparaisons est-il le plus petit ? Quel est, dans ce cas, le nombre de comparaisons faites pour une liste contenant \(n\) entiers ?

🖊️ 2) Pour quelles valeurs recherchées le nombre de comparaisons est-il le plus grand ? Quel est, dans ce cas, le nombre de comparaisons faites pour une liste contenant \(n\) entiers ?

Vocabulaire

La situation la plus défavorable est appelée le pire cas. Dans ce cas, la complexité en fonction de la longueur \(n\) des données est notée \(O(n)\).

La situation la plus favorable est appelée le meilleur cas. Dans ce cas, la complexité en fonction de la longueur \(n\) des données est notée \(o(n)\).

Coût pour la recherche par dichotomie

Reprendre la fonction recherche_dichotomique(E,L)

🖊️ 1) Pour une liste donnée, quel est le meilleur cas et quel est le pire cas ?

🖊️ 2) Quel est le nombre d'itérations effectuée par la boucle while pour une liste contenant \(n\) entiers, dans le pire cas ?

Afficher la correction

Dans le pire des cas (si l'entier recherché n'est pas dans la liste), le nombre de comparaisons faites par l'algorithme est le nombre de fois qu'il faut diviser la longueur de la liste par 2 pour arriver à une sous-liste de longueur 1.

Autrement dit, on cherche \(a\) tel que \(\dfrac{n}{2^a} = 1\), c'est à dire \(n = 2^a\). Ce que l'on peut écrire \(a = \log_2 n\). \(\log_2\) étant une fonction mathématique particulière.

Comparaison des deux algorithmes

🖥️ 1) Ecrire une fonction qui prend un nombre entier en paramètre et renvoie la liste des nombre entier de 1 à ce nombre.

🖥️ 2) En reprenant certaines fonctions précédantes et en complétant avec d'autres fonction ecrire un programme qui permet de compléter le tableau ci-dessous.

Longueur de la liste Complexité pour la recherche séquentielle dans le pire cas Complexité pour la recherche par dichotomie dans le pire cas
1000
10000
100000
1000000
Afficher la correction 
def liste_1_a_n(n:int)->list:
    liste = []
    for i in range(1,n+1):
        liste.append(i)
    return liste

def recherche_seq_triee(E, L):
    compteur = 0
    i = 0
    val = L[0]
    while i < len(L)-1 and L[i] < E :
        compteur = compteur + 1
        i = i + 1
    if L[i] == E:
        reponse = i
    else:
        reponse = -1
    print("Nombre d'itérations algo séquantiel : " + str(compteur))
    return reponse

def recherche_dichotomique(E,L):
    compteur = 0
    a = 0
    b = len(L)-1
    m = (a + b) //2
    while b - a > 0 and E != L[m]:
        compteur = compteur + 1
        if E < L[m]:
            b = m-1
        else:
            a = m+1
        m = (a + b) //2
    print("Nombre d'itérations algo dichotomique : " + str(compteur))
    if E == L[m]:
        return m
    else :
        return -1

# Programme principal
print('------------------------------')
n = 1000
print('Pour la liste de longueur ' + str(n))
l = liste_1_a_n(n)
recherche_seq_triee(n + 1, l)
recherche_dichotomique(n + 1, l)

print('------------------------------')
n = 10000
print('Pour la liste de longueur ' + str(n))
l = liste_1_a_n(n)
recherche_seq_triee(n + 1, l)
recherche_dichotomique(n + 1, l)

print('------------------------------')
n = 100000
print('Pour la liste de longueur ' + str(n))
l = liste_1_a_n(n)
recherche_seq_triee(n + 1, l)
recherche_dichotomique(n + 1, l)

print('------------------------------')
n = 1000000
print('Pour la liste de longueur ' + str(n))
l = liste_1_a_n(n)
recherche_seq_triee(n + 1, l)
recherche_dichotomique(n + 1, l)