Complexité en espace

I. Problème de l'approche empirique

La complexité en espace est difficile à évaluer empiriquement pour plusieurs raisons :

Les données sont réparties dans 2 zones différentes : le tas et la pile. Le tas est notamment utilisé pour les allocations d'objets, et la pile est notamment utilisée pour les variables locales des fonctions. Ainsi, chaque appel de fonction fait augmenter la taille de la pile, ce qui peut s'avérer catastrophique dans le cas de certaines fonctions récursives ;
Il existe des outils permettant de connaître la taille allouée à un processus, mais le système alloue en général une taille de base assez importante, qui masque donc les différences d'espace mémoire utilisé pour les faibles tailles.
Il est important de savoir quand de nouveaux objets sont créés, et ce n'est pas toujours évident. Comparer par exemple les 2 programmes suivants :
```
liste = [1, 2, 3]
liste2 = liste
```
```
liste = [1, 2, 3]
liste2 = liste[:]
```
Indice : Python tutor peut aider à comprendre la différence.

Pour vérifier les risques en cas de récursivité, vous pouvez tester le programme complexiteEspace01factorielle.py.

II. Déterminer une complexité en espace

2 implantations du même algorithme peuvent avoir des complexités en espace fort différentes. C'est le cas par exemple des 2 versions de l'algorithme de tri rapide données dans le fichier complexiteEspace02triRapide.py.

Exercice : à partir du programme ci-dessus :

Déterminez où chacun de ces 2 algorithmes crée des données, et en déduire la complexité en espace de chacun
Modifiez ces 2 algorithmes pour qu'ils renvoient l'espace utilisé, puis tracez les courbes permettant de les comparer
Rajoutez à cette comparaison l'algorithme de tri à bulle donné dans le fichier complexiteEspace03triBulle.py.