Complexité d’un algorithme

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.

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 ?

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

4.2. Le saviez-vous ?

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

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 :

Trouver l’élément maximum de la partie du tableau restant à trier, c’est-à-dire le maximum de table[i] à table[n-1]
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

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 :

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

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

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]

Combien de fois la boucle
```
for i in range(n)
```
sera t'elle répétée ?

Combien de fois la boucle
```
for j in range(0, n-i-1):
```
quand
```
i =0
```
sera t'elle répétée ?

Combien de fois la boucle
```
for j in range(0, n-i-1):
```
quand
```
i = 1
```
sera t'elle répétée ?

Combien de fois la boucle
```
for j in range(0, n-i-1):
```
quand
```
i = 2
```
sera t'elle répétée ?

Combien de fois la boucle
```
for j in range(0, n-i-1):
```
quand
```
i = n-2
```
sera t'elle répétée ?

Combien de fois la boucle
```
for j in range(0, n-i-1):
```
quand
```
i = n-1
```
sera t'elle répétée ?

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

Quelle est la classe de complexité de cet algorithme ?

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.

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

Quelle est la classe de complexité de cet algorithme ?

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]

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 ?

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) \)

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 ?

Complexité d’un algorithme

1. Introduction

2. Objectif de la séance :

3. Qu’est ce que la complexité ?

3.1. Définition

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

4. Notion de complexité

4.1. Travail à faire : Un peu d’histoire

4.2. Le saviez-vous ?

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

5.1. Principe

5.2. Travail à faire : Exemple

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

5.4. Résultats mathématiques à retenir

6. Calcul et classe de complexité

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

6.2. Travail à faire : Tri à bulle

6.3. Travail à faire : Un programme bizarre

7. Complexité du tri par insertion

7.1. Travail à faire : Rappel

7.2. Algorithme

7.3. Travail à faire : Calcul

7.4. Travail à faire : Programmation

8. Recherche dichotomique

8.1. Programme

8.2. Travail à faire : Calcul

8.3. Travail à faire : Programmation