Logo de kxs.frCours d'informatique pour le lycée et la prépa

Bilan

Nous avons vu trois types de structure de données linéaires : les listes, les piles et les files. Enfin nous avons revu les dctionnaires ou tableaux associatifs. L'avantage des tableaux associatifs est qu'ils utilisent une table de hashage qui permet de trouver une clé en un temps indépendant de la taille du tableau.

Complexité des opérations

Nous allons résumer les complexités de différentes opérations dans les structures de données en fonction de leur implémentation.

Liste (avec un tableau dynamique)

Ceci est la façon dont python implémente ses listes.

Action Complexité
Insertion en fin de liste O(1)
Insertion à la position i O(n)
Insertion en début de liste O(n)
Suppression du dernier élément O(1)
Suppression de l'élément i O(n)
Recherche d'un élément O(n)

Liste (avec une liste chainée)

Nous avons utilisé cette implémentation dans le chapitre sur les listes.

Action Complexité
Insertion en fin de liste O(1)
Insertion à la position i O(n)
Insertion en début de liste O(1)
Suppression du dernier élément O(1)
Suppression de l'élément i O(n)
Recherche d'un élément O(n)

Pile (peu importe l'implémentation)

On ne s'intéresse ici qu'à l'empilement et au dépilement car si on veut faire davantage de choses, on utilisera une liste.

Action Complexité
Empilement O(1)
Depilement O(1)

File (avec une liste chainée)

Ici on considère une File implémentée avec une liste chaînée car avec un tableau dynamique, cela ne serait pas intéressent du point de vue de la complexité. Comme pour la pile, on ne s'intéresse ici qu'à l'enfilement et au défilement car si on veut faire davantage de choses, on utilisera une liste.

Action Complexité
Enfilement O(1)
Defilement O(1)

Dictionnaire

Les dictionnaires de Python ou les tableaux associatifs.

Action Complexité
Ajout d'un élément O(1)
Suppression d'un élément O(1)
Accès à un élément O(1)
Recherche d'un élément à partir de sa clé O(1)
Recherche d'un élément à partir de sa valeur O(n)

1) Expliquez simplement la complexité des recherches dans les deux implémentations de liste et dans les dictionnaires.

Dans les deux implémentations de listes, il est nécessaire d'accéder à tous les éléments de la liste pour trouver l'élément cherché. Cela prend donc un temps qui est proportionnel à la taille de la liste : O(n).

Dans un dictionnaire, la table de hashage permet d'accéder quasiment instantanément à l'élément cherché. Le temps est donc indépendant de la taille de la liste : O(1).

Pour terminer, voici un programme qui permet de comparer le temps de recherche dans une liste et dans un dictionnaire :

import time

for p in [3,4,5,6,7]:

    n = 10**p
    print("n =", n, ":")

    # Création d'une liste [0, 1, ..., n]
    liste = list(range(n))
    # Création d'un dictionnaire {0: None, 1: None, ..., n: None}
    dictionnaire = dict.fromkeys(range(n))

    debut = time.perf_counter()
    # Recherche infructueuse dans la liste
    'a' in liste
    fin = time.perf_counter()
    temps = round((fin - debut)*1000, 3)

    print("Temps d'exécution pour la liste :", temps, "ms")

    debut = time.perf_counter()
    # Recherche infructueuse dans le dictionnaire
    'a' in dictionnaire
    fin = time.perf_counter()
    temps = round((fin - debut)*1000, 3)

    print("Temps d'exécution pour le dictionnaire :", temps, "ms")
    print()

2) Recopiez et exécutez ce programme puis analysez les résultats.

Voici le résultat du programme :

n = 1000 :
Temps d'exécution pour la liste : 0.022 ms
Temps d'exécution pour le dictionnaire : 0.001 ms

n = 10000 :
Temps d'exécution pour la liste : 0.198 ms
Temps d'exécution pour le dictionnaire : 0.002 ms

n = 100000 :
Temps d'exécution pour la liste : 2.073 ms
Temps d'exécution pour le dictionnaire : 0.002 ms

n = 1000000 :
Temps d'exécution pour la liste : 17.668 ms
Temps d'exécution pour le dictionnaire : 0.002 ms

n = 10000000 :
Temps d'exécution pour la liste : 144.379 ms
Temps d'exécution pour le dictionnaire : 0.001 ms

On constate que le temps de recherche dans le dictionnaire ne varie pas significativement en fonction de n. La complexité est donc en O(1).

Par ailleurs le temps de recherche dans la liste est approximativement multiplié par 10 à cahque étape. Il est donc linéaire en fonction de n (qui est également multiplié par 10 à cahque étape) et la complexité est en O(n).

3) Avec un programme similaire comparez le temps d'insertion d'un élément en début et en fin de liste.

Voici un programme :

import time

for p in [3,4,5,6,7]:

    n = 10**p
    print("n =", n, ":")

    # Création d'une liste [0, 1, ..., n]
    liste = list(range(n))

    debut = time.perf_counter()
    # Ajout d'un éléménet en fin de liste
    liste.append('a')
    fin = time.perf_counter()
    temps = round((fin - debut)*1000, 3)

    print("Temps d'insertion en fin de liste :", temps, "ms")

    debut = time.perf_counter()
    # Ajout d'un éléménet en début de liste
    liste.insert(0,'a')
    fin = time.perf_counter()
    temps = round((fin - debut)*1000, 3)

    print("Temps d'insertion en début de liste :", temps, "ms")
    print()

Et le résultat :

n = 1000 :
Temps d'insertion en fin de liste : 0.001 ms
Temps d'insertion en début de liste : 0.002 ms

n = 10000 :
Temps d'insertion en fin de liste : 0.003 ms
Temps d'insertion en début de liste : 0.01 ms

n = 100000 :
Temps d'insertion en fin de liste : 0.026 ms
Temps d'insertion en début de liste : 0.081 ms

n = 1000000 :
Temps d'insertion en fin de liste : 0.054 ms
Temps d'insertion en début de liste : 1.653 ms

n = 10000000 :
Temps d'insertion en fin de liste : 0.246 ms
Temps d'insertion en début de liste : 11.697 ms

On constate que le temps d'insertion en début de liste est approximativement multiplié par 10 à cahque étape. Ce qui confirme une complexité en O(n).

Le temps d'insertion en fin de liste n'est par contre pas constant. Il n'est pas non plus linéaire.