human
Veuillez expliquer ce qu'est "l'algorithme en ligne"
gpt
En informatique, un algorithme en ligne est un algorithme qui peut traiter son entrée pièce par pièce de manière sérielle, c'est-à-dire dans l'ordre dans lequel l'entrée est transmise à l'algorithme, sans avoir l'entièreté de l'entrée disponible dès le départ.
En revanche, un algorithme hors ligne reçoit toutes les données du problème depuis le début et doit produire une réponse qui résout le problème en question. En recherche opérationnelle, le domaine dans lequel les algorithmes en ligne sont développés est appelé optimisation en ligne.
À titre d'exemple, considérons les algorithmes de tri tri par sélection et tri par insertion : le tri par sélection sélectionne à plusieurs reprises l'élément minimum dans le reste non trié et le place au premier plan, ce qui nécessite l'accès à l'intégralité de l'entrée ; c'est donc un algorithme hors ligne. D'autre part, le tri par insertion considère un élément d'entrée par itération et produit une solution partielle sans tenir compte des éléments futurs. Ainsi, le tri par insertion est un algorithme en ligne.
Notez que le résultat final d'un tri par insertion est optimal, c'est-à-dire une liste correctement triée. Pour de nombreux problèmes, les algorithmes en ligne ne peuvent pas égaler les performances des algorithmes hors ligne. Si le rapport entre les performances d'un algorithme en ligne et d'un algorithme hors ligne optimal est borné, l'algorithme en ligne est dit compétitif.
Tous les algorithmes hors ligne n'ont pas d'équivalent en ligne efficace.