1. Introduction

Il est possible de trier une liste ou un tableau à l’aide de l’algorithme de tri par sélection ou de celui par insertion. Mais ces algorithmes permettent-ils de trier de grandes quantité de données ou demandent-ils trop de temps pour pouvoir être réellement mis en œuvre ?

2. Objectif de la séance :

Comprendre la notion de coût d’un algorithme et calculer le coût de quelques algorithmes caractéristiques.

3. Qu’est ce que la complexité ?

3.1. Définition

Lorsqu’on doit étudier une grande quantité de données (moyenne, tri, …​), il devient important de savoir le temps qui va être nécessaire à l’algorithme pour effectuer ce tri.

On parle de la complexité de l’algorithme.

Même si de nombreux facteurs influencent ce temps (processeur, capacité mémoire etc..), un élément important est le nombre d’opérations élémentaires que doit effectuer l’algorithme (affectation, comparaison par exemple).

Lorsqu’on trie de grandes quantités de données, ce critère est important en effet avec le tri par insertion pour trier \( 1000 \) valeurs, il faut effectuer environ \( 1000000 \) opérations !

Plus généralement, pour trier \( n \) valeurs, on effectue environ \( n^{2} \) __opérations.

3.2. Travail à faire : Comparaison de deux alogrithmes de tri

Consultez l’article de Wikipédia sur les algorithmes de tri et en particulier le paragraphe sur la complexité et celui sur la comparaison des algorithmes puis répondez aux questions suivantes :

Avec l’algorithme de tri par tas, combien d’opérations effectue-t-on pour trier \( 10^{6} \) valeurs ?


  1. 106
  2. ≈20.106
  3. 109
  4. 1012

Dans le pire des cas, avec l’algorithme de tri par sélection, combien d’opérations effectue-t-on pour trier \( 10^{6} \) valeurs ?


  1. 106
  2. ≈20.106
  3. 109
  4. 1012

L’algorithme de tri par tas vous semble-t-il plus efficace ?


  1. OUI
  2. NON

4. Notion de complexité

4.1. Travail à faire : Un peu d’histoire

Consultez les paragraphes Histoire et Différentes approches l’article de Wikipédia la complexité des algorithmes puis répondez aux questions suivantes :

Quel informaticien a, le premier, proposé un calcul du coût indépendant de la machine utilisée ?


  1. Donald Knuth
  2. Allan Turing
  3. Gilles Dowek

Quelle est l’approche la plus classique de calcul du temps ?


  1. Calcul dans le pire des cas
  2. Calcul en moyenne
  3. Calcul dans le meilleur cas

4.2. Le saviez-vous ?

Actuellement, les quantités de données analysées augmentent très rapidement, on parle maintenant de big data.

17800

5. Complexité de l’algorithme de tri par sélection

5.1. Principe

Nous allons donc calculer le coût de l’algorithme de tri par sélection dans le pire des cas en comptant le nombre d’opérations élémentaires qui doivent être effectuées.

L’algorithme de tri par sélection est donc basé sur la répétition des instructions :

  1. Trouver l’élément maximum de la partie du tableau restant à trier, c’est-à-dire le maximum de table[i] à table[n-1]

  2. Echanger cet élément avec l’élément table[i] si nécessaire. Comme on se place dans le pire des cas, on suppose que cet échange a toujours lieu.

5.2. Travail à faire : Exemple

Nous allons évaluer ce nombre d’opérations pour l’algorithme de tri par sélection.

10

22

3

8

15

26

24


  1. Pour échanger deux éléments, on effectue affectations.
  2. A l’étape 1, on effectue comparaisons.
  3. A l’étape 1, on effectue donc, au total opérations élémentaires.
  4. A l’étape 2, on effectue donc, au total opérations élémentaires.
  5. Pour trier le tableau en suivant l’algorithme de tri par sélection, on utilise donc, au total, opérations élémentaires.

5.3. Travail à faire : Cas général

On va maintenant évaluer le nombre d’opérations nécessaires dans le cas général d’un tableau comprenant \( n \) éléments. Pour simplifier, on va supposer que les affectations sont négligeables et ne compter que les comparaisons :


Pour trouver le maximum d’un tableau de n valeurs, combien de comparaisons sont nécessaires ?

  • A l'étape 1, pour trouver le maximum du tableau restant à trier, combien de comparaisons sont nécessaires ?
  • A l'étape i, combien de comparaisons effectue-t-on ?

  • 5.4. Résultats mathématiques à retenir

    • L’ordre de grandeur ne change pas si on ajoute ou enlève quelques uns des premiers termes

    • \( 1+2+…+n=n \frac{(n+1)}{2} \) :
      L’ordre de grandeur de la somme des \( n \) premiers entiers est \( n^{2}\)

    • \( 1+1+…​.+1 = n \) :
      L’ordre de grandeur est \( n \)

    • \( n+ n+…​+ n= n^{2} \) :
      L’ordre de grandeur est \( n^{2}\)

    6. Calcul et classe de complexité

    Pour calculer la complexité d’un algorithme, on recherche le nombre maximum d’intructions qui seront exécutées dans le pire des cas.

    On généralise ensuite en recherchant l’ordre de grandeur de la complexité ou classe de complexité noté \( \mathcal{O}(n) \) :

    Notation Classe de complexité

    \(\mathcal{O}(1)\)

    constante (indépendant de la taille de la donnée)

    \(\mathcal{O}(\log(n))\)

    logarithmique

    \(\mathcal{O}(n)\)

    linéaire

    \(\mathcal{O}(n\log(n))\)

    quasi-linéaire

    \(\mathcal{O}(n^{2})\)

    quadratique

    \(\mathcal{O}(n^{3})\)

    cubique

    \(\mathcal{O}(n^{p})\)

    polynomiale

    \(\mathcal{O}(2^{n})\)

    exponentielle

    \(\mathcal{O}(!n)\)

    factorielle

    6.1. Travail à faire : Recherche d’un élément dans une liste

    Soit l’algorithme de recherche d’un élément dans une liste :

    fonction trouver(x, liste):
        a_trouver ← Faux
        n ← longeur(liste)
        Pour i allant de 0 à n:
              Si liste[i]=x alors
                    a_trouver ← Vrai
              FinSi
        Fin Pour
        retourner a_trouver
    Fin

    1. Combien d'instructions élémentaires seront exécutées au total dans le meilleurs des cas :
    2. Combien d'instructions élémentaires seront exécutées au total dans le pire des cas :
    3. Quelle est la classe de complexité de cet algorithme ?
    4.  \(\mathcal{O}(1)\)      \(\mathcal{O}(\log(n))\)       \(\mathcal{O}(n)\)       \(\mathcal{O}(n\log(n))\)      \(\mathcal{O}(n^{2})\)

    Un peu d’aide
    • La boucle for est constituée de deux instructions : une affectation et une comparaison

    • Dans le meilleur des cas, on ne trouve jamais la valeur x dans la liste, donc on effectue jamais l’affection a_trouver ← Vrai

    • Dans le pire des cas, la liste ne contient que des valeurs x, donc on effectue n fois l’affection a_trouver ← Vrai

    Soit l’algorithme de recheche d’un élément dans une liste :

    fonction trouver(x, liste):
        a_trouver ← Faux
        Tant que a_trouver = Faux
              Si liste[i]=x alors
                    a_trouver ← Vrai
              FinSi
        Fin Tant que
        retourner a_trouver
    Fin

    1. Combien d'instructions élémentaires seront exécutées au total dans le meilleurs des cas :
    2. Combien d'instructions élémentaires seront exécutées au total dans le pire des cas :
    3. Quelle est la classe de complexité de cet algorithme ?
    4.  \(\mathcal{O}(1)\)      \(\mathcal{O}(\log(n))\)       \(\mathcal{O}(n)\)       \(\mathcal{O}(n\log(n))\)      \(\mathcal{O}(n^{2})\)

    Un peu d’aide
    • La boucle Tant que est une comparaison

    • Dans le meilleur des cas, la valeur x est le premier élément de la liste, la boucle ne tourne qu’une seule fois et on affecte a_trouver ← Vrai

    • Dans le pire des cas, la valeur x est le dernier élément de la liste, la boucle tourne n fois et on affecte pas a_trouver ← Vrai
      Remarque : Si x n’est pas présent dans la liste, la boucle ne s’arrête jamais !

    6.2. Travail à faire : Tri à bulle

    Soit l’algorithme suivant :

    def tri_bulle(tab):
        n = len(tab)
        # Traverser tous les éléments du tableau
        for i in range(n):
            for j in range(0, n-i-1):
                # échanger si l'élément trouvé est plus grand que le suivant
                if tab[j] > tab[j+1] :
                    tab[j], tab[j+1] = tab[j+1], tab[j]

    1. Combien de fois la boucle

      for i in range(n)

      sera t'elle répétée ?

    2. Combien de fois la boucle

      for j in range(0, n-i-1):
      quand
      i =0

      sera t'elle répétée ?

    3. Combien de fois la boucle

      for j in range(0, n-i-1):
      quand
      i = 1

      sera t'elle répétée ?

    4. Combien de fois la boucle

      for j in range(0, n-i-1):
      quand
      i = 2

      sera t'elle répétée ?

    5. Combien de fois la boucle

      for j in range(0, n-i-1):
      quand
      i = n-2

      sera t'elle répétée ?

    6. Combien de fois la boucle

      for j in range(0, n-i-1):
      quand
      i = n-1

      sera t'elle répétée ?

    7. Evaluer la complexité totale de l'algorithme, c'est à dire le nombre de fois ou la comparaison va être effectuée.

    8. Quelle est la classe de complexité de cet algorithme ?
    9.  \(\mathcal{O}(1)\)      \(\mathcal{O}(\log(n))\)       \(\mathcal{O}(n)\)       \(\mathcal{O}(n\log(n))\)      \(\mathcal{O}(n^{2})\)

    Un peu d’aide
    • L’ordre de grandeur ne change pas si on ajoute ou enlève quelques uns des premiers termes

    • \( 1+2+…+n=n \frac{(n+1)}{2} \) :
      L’ordre de grandeur de la somme des \( n \) premiers entiers est \( n^{2}\)

    6.3. Travail à faire : Un programme bizarre

    Soit la fonction python suivante :

    def fonction(n):
        c = 0
        while n>0:
          c+=1
          n = n//2
        return c
    
    for i in range(1, 1001):
      print(i, " : ", fonction(i))

    La variable c compte le nombre de fois ou la boucle est répétée. A quelques instructions près, elle donne donc le résultat de la complexité de cet algorithme.

    • Coder et tester ce programme. Que représente les variables i et c ?

    • Quelle est sa classe de complexité ?



     \(\mathcal{O}(1)\)      \(\mathcal{O}(\log(n))\)       \(\mathcal{O}(n)\)       \(\mathcal{O}(n\log(n))\)      \(\mathcal{O}(n^{2})\)
    Un peu d’aide
    • LA chaque itération de la boucle, on divise par deux le nombre d’itérations restantes.

    • La fonction mathématique \( \log_{2}(n) = \frac{\log(n)}{\log(2)} \)

    7. Complexité du tri par insertion

    7.1. Travail à faire : Rappel

    C’est le tri du joueur de cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite…​

    Le principe du tri par insertion est donc d’insérer à la \( n_{ième} \) itération le \( n_{ième} \) élément à la bonne place.

    Tableau 1 10 22 3 8 15 26 24
    Etape 1 du tri : où placer 22 22 10 3 8 15 26 24
    Etape 2 : où placer 3 ? 22 10 3 8 15 26 24
    Etape 3 : où placer 8 ? 22 10 8 3 15 26 24
    Etape 4 : où placer 15 ? 26 24
    Etape 5 : où placer 26 ? 24
    Etape 6 : où placer 24 ?

    7.2. Algorithme

    fonction tri_insertion(liste)
        n ← longueur(liste)
        Pour i de 1 à n - 1 :
            # mémoriser liste[i] dans x
            x ← liste[i]
            # décaler vers la droite les éléments de liste[0]..liste[i-1] qui sont plus grands que x en partant de liste[i-1]
            j ← i
            Tant que j > 0 et liste[j - 1] > x :
                liste[j] ← liste[j - 1]
                j ← j - 1
            # placer x dans le "trou" laissé par le décalage
            liste[j] ← x
        retourner liste

    7.3. Travail à faire : Calcul

    Le pire des cas consiste à trier une liste inversement triée :

    • [1, 2, 3, 4, 5, 6] à trier dans l’ordre décroissant

    • [6, 5, 4, 3, 2, 1] à trier dans l’odre croissant

      Dans le cas d'une liste de 2 éléments, combien de déplacements va-t-on effectuer pour trier la liste ?
    1. 0
    2. 1
    3. 2
      Dans le cas d'une liste de 3 éléments, combien de déplacements va-t-on effectuer pour trier la liste ?
    1. 0
    2. 1
    3. 2
    4. 3
      Dans le cas d'une liste de 4 éléments, combien de déplacements va-t-on effectuer pour trier la liste ?
    1. 3
    2. 4
    3. 5
    4. 6
      Dans le cas d'une liste de 5 éléments, combien de déplacements va-t-on effectuer pour trier la liste ?
    1. 8
    2. 9
    3. 10
    4. 11
      Dans le cas d'une liste de \( n \) éléments, combien de déplacements va-t-on effectuer pour trier la liste ?
    1. \( n \)
    2. \( n^{2} \)
    3. \( n \frac{(n-1)}{2} \)
    4. \( n \frac{(n+1)}{2} \)

    Quelle est la classe de complexité de cet algorithme ?

    1.  \(\mathcal{O}(1)\)    
    2.  \(\mathcal{O}(\log(n))\)     
    3.  \(\mathcal{O}(n)\)     
    4.  \(\mathcal{O}(n\log(n))\)    
    5.  \(\mathcal{O}(n^{2})\)

    Un peu d’aide
    • L’ordre de grandeur ne change pas si on ajoute ou enlève quelques uns des premiers termes

    • \( 1+2+…+n=n \frac{(n+1)}{2} \) :
      L’ordre de grandeur de la somme des \( n \) premiers entiers est \( n^{2}\)

    • De manière générale, lorsque deux boucles sont imbriquées, le nombre maximum d’itération est \( n^{2} \) :

    fonction boucle_imbriquee(n)
        c ← 0
        Pour i=0 à n-1:
            Pour j=0 à n-1
              c ← c + 1
        retourner c
    
    Afficher(boucle_imbriquee(5)
    
    Sortie : 25
    
    Afficher(boucle_imbriquee(10)
    
    Sortie : 100

    7.4. Travail à faire : Programmation

    • Coder et tester la fonction tri_insertion(liste) pour trier dans l’ordre croissant les éléments de la liste donnée en argument

    • Modifier le code pour que la fonction retourne le nombre de permutations effectuées

    • Tester la fonction avec les listes suivantes :

      • [6, 5, 4, 3, 2, 1] doit retourner \( 15 \)

      • [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] doit retourner \( 45 \)

      • [*range(20,0,-1)] doit retourner \( 190 \)

      • [*range(50,0,-1)] doit retourner \( 1225 \)

      • [*range(100,0,-1)] doit retourner \( 4950 \)

    • Vérifier que la complexité de cet algorithme est de \(n \frac{(n-1)}{2} \) et que sa classe de complexité est \(\mathcal{O}(n^{2})\)

    Correction
    • Les tests sont effectués en utilisant des assertions :

    def tri_insertion(liste):
        n = len(liste)
        c=0 # compteur
        for i in range(1,n):
            #print(i, " : ", liste)
            x = liste[i]
            j = i
            while j > 0 and liste[j - 1] > x :
                liste[j] = liste[j - 1]
                c+=1 # une permutation de plus
                #print(c) # affichage nbr de permutations
                j = j - 1
            liste[j] = x
        #print(liste) # affiche la liste triée
        return c
    
    a_trier = [6, 5, 4, 3, 2, 1]
    assert tri_insertion(a_trier) == 15, "Tri de 6 éléments"
    
    a_trier = [10,9, 8, 7, 6, 5, 4, 3, 2, 1]
    assert tri_insertion(a_trier) == 45, "Tri de 10 éléments"
    
    a_trier = [*range(20,0,-1)]
    assert tri_insertion(a_trier) == 190, "Tri de 20 éléments"
    
    a_trier = [*range(50,0,-1)]
    assert tri_insertion(a_trier) == 1225, "Tri de 50 éléments"
    
    a_trier = [*range(100,0,-1)]
    assert tri_insertion(a_trier) == 4950, "Tri de 100 éléments"
    
    print("Tests OK !")

    8. Recherche dichotomique

    La recherche dichotomique, ou recherche par dichotomie, est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié. Le principe est le suivant :

    • comparer l’élément avec la valeur de la case au milieu du tableau ;

    • si les valeurs sont égales, la tâche est accomplie,

    • sinon on recommence dans la moitié du tableau pertinente.

    Par exemple, on recherche 4 dans la liste [1, 3, 4, 6, 7, 8, 10, 13, 14]

    • On se place au milieu de la liste : 7

    • On compare 4 à 7 : 4 < 7, on recherche 4 dans la sous-liste [1, 3, 4, 6]

    • On se place au milieu de la liste : 3

    • On compare 4 à 3 : 4 > 3, on recherche 4 dans la sous-liste [4, 6]

    Binary search into array

    8.1. Programme

    def dichotomie(liste, x):
      find = False
      start = 0
      end = len(liste)-1
      m = (end - start)//2
      while end>=start and not find:
        #print(m)
        if liste[m] == x:
          find = True
        elif x > liste[m]:
          start = m+1
        elif x < liste[m]:
          end = m-1
        m = (end - start)//2 + start
      if find:
        return m
      return -1
    
    liste = [*range(1,50,4)]
    print(liste)
    
    pos = dichotomie(liste, 17)
    print("Recherche de l'élément 17 :")
    if pos!=1:
      print("Trouvé à la position ", pos)
    else:
      print("Pas trouver")

    8.2. Travail à faire : Calcul

    • Calculer la complexité de l’algorithme de recherche dichotomique dans le pire des cas

    Quelle est la classe de complexité de cet algorithme ?

    1.  \(\mathcal{O}(1)\)    
    2.  \(\mathcal{O}(\log(n))\)     
    3.  \(\mathcal{O}(n)\)     
    4.  \(\mathcal{O}(n\log(n))\)    
    5.  \(\mathcal{O}(n^{2})\)

    Un peu d’aide
    • L’ordre de grandeur ne change pas si on ajoute ou enlève quelques uns des premiers termes

    • \( 1+2+…+n=n \frac{(n+1)}{2} \) :
      L’ordre de grandeur de la somme des \( n \) premiers entiers est \( n^{2}\)

    • De manière générale, lorsque deux boucles sont imbriquées, le nombre maximum d’itération est \( n^{2} \) :

    fonction boucle_imbriquee(n)
        c ← 0
        Pour i=0 à n-1:
            Pour j=0 à n-1
              c ← c + 1
        retourner c
    
    Afficher(boucle_imbriquee(5)
    
    Sortie : 25
    
    Afficher(boucle_imbriquee(10)
    
    Sortie : 100

    8.3. Travail à faire : Programmation

    • Coder et tester la fonction dichotomie(liste, x) pour rechercher la valeur x parmi les éléments de la liste donnée en argument

    • Modifier le code pour que la fonction retourne le nombre d’itérations effectuées lors de la recherche

    • Tester la fonction avec le programme suivant qui affiche le nombre d’itérations nécessaire pour rechercher chaque élément de la liste ainsi que le nombre maximum d’itérations :

    def dichotomie(liste, x):
      ...
      return c
    
    liste = [*range(1,100)]
    print(liste)
    
    max_iterations = 0
    for i in liste:
      nb = dichotomie(liste, i)
      if nb>max_iterations:
        max_iterations = nb
      print(f"Recherche de l'élément {i} :")
      print("  Touver en ", nb, " coups")
    
    print("nombre maximum d'itérations : ", max_iterations)
    • Vérifier que la complexité de cet algorithme est \( \log(n) \) et sa classe de complexité \(\mathcal{O}(\log(n))\)

    Correction
    def dichotomie(liste, x):
      find = False
      start = 0
      end = len(liste)-1
      m = (end - start)//2
      c = 0
      while end>=start and not find:
        #print(m)
        if liste[m] == x:
          find = True
        elif x > liste[m]:
          start = m+1
        elif x < liste[m]:
          end = m-1
        c +=1
        m = (end - start)//2 + start
      return c
    
    liste = [*range(1,100)]
    print(liste)
    
    max_iterations = 0
    for i in liste:
      nb = dichotomie(liste, i)
      if nb>max_iterations:
        max_iterations = nb
      print(f"Recherche de l'élément {i} :")
      print("  Touver en ", nb, " coups")
    
    print("nombre maximum d'itérations : ", max_iterations)

    Ce programme retourne \( 7 \) pour le maximum d’itérations lorsque la taille des données est de \( 100 \). On vérifie bien ici que la complexité est logarithmique car

    \( \log_{2}(100) = 6,64 \approx 7 \)

    Pour s’en assurer, vous pouvez modifier la taille de la liste et vérifier que pour \( n \) éléments, le maximum d’itérations est toujours égal à \( \log_{2}(n) \)


    the_end.jpg