s
19 708 Pages

en informatique un algorithme disent-ils sur place ou en place quand il est capable de transformer une structure de données en utilisant seulement un petit espace et constant mémoire extras. Les données d'entrée sont généralement remplacées par le résultat produit lors de l'exécution de l'algorithme.

Un algorithme est parfois appelé officieusement sur place quand il écrase son entrée avec sa sortie. En fait, cela ne suffit pas (comme le cas de quicksort) ni nécessaire; la quantité d'espace occupé par la sortie peut être constante, ou il pourrait même ne pas être quantifiés, par exemple dans le cas du flux de sortie. D'autre part, parfois, il pourrait être plus pratique de quantifier l'espace occupé par les résultats de la production et de déterminer si l'algorithme est défini comme sur place, comme on le voit dans l'exemple ci-dessous inversion.

Les algorithmes sur place sont plus efficaces en termes de mémoire et, souvent, même en termes de CPU, que leurs homologues non sur place et donc ils ont tendance à être préféré à ce dernier.

exemple

Supposons que nous devons renverser un tableau de n éléments. Ceci est un moyen simple:

fonction vers le bas (a [0..n])
alloue b [0..n]
pour la de 0 à n
b [n - i] = a [i]
retour b

Malheureusement, cela nécessite O (n) Espace pour créer b et l'allocation est souvent un processus lent. Si le résultat du programme on n'a plus besoin de stocker à Nous pouvons l'emporter avec son revers en utilisant un algorithme sur place:

fonction Vers le bas en place ([0..n])
pour la de 0 à int(N / 2)
swap (a [i], a [n-i])

Certains algorithmes sur le site

Voici un certain nombre d'algorithmes de tri qui fonctionnent sur le site:

  • Bubble tri
  • Le tri par insertion
  • quicksort
  • sorte de sélection
  • compter tri. Il a également une contrepartie sur place, un peu plus efficace en termes de CPU, mais avec le même complexité (Linéaire)
  • sorte Heap
  • Trier Shell

D'autres projets

Activité wiki récente

Aidez-nous à améliorer BooWiki
Commencez