« Programmation algorithmique/Tris » : différence entre les versions
Contenu supprimé Contenu ajouté
→Tri de Shell : ajout d'infos (renvoi vers l'extérieur) |
→Tri de fichiers en mémoire externe : ajout d'info et changement du niveau de la sous-section |
||
Ligne 159 :
*'''Complexité en temps :''' la complexité en temps de ce tri dépend de son paramétrage et, selon les cas, on trouve <math>O(n^{2})</math>, <math>O(n^{3/2})</math>, ou <math>O(n^{4/3})</math> par exemple. Voir [[w:Shellsort]], [[w:Tri_de_Shell]] ou ''The art of Computer Programming volume 3, Donald E. Knuth, Addison-Wesley''.
Cette section concerne le tri de données trop grandes pour être stockées en mémoire vive de l'ordinateur, et étant donc stockées sur des supports physiques comme des disques durs.
Notons que les périphériques de stockage sont généralement plus lents que la mémoire vive. Par ailleurs, autrefois le support externe de référence était la bande magnétique, avec pour résultat que le temps d'accès à une donnée dépend de sa position sur la bande, alors qu'en mémoire vive, le temps d'accès aux données ne dépend pas de leur emplacement (si l'on fait abstraction des questions de mémoire tampon).
[[Catégorie:Programmation Algorithmique (livre)]]
| |||