Parcours séquentiels

Quiz
Classe(s) : 1re Générale | Thème(s) : Algorithmes fondamentaux

Parcours séquentiels

On dispose d'un algorithme qui cherche la valeur maximale d'une liste non triée.

On mesure le temps qu'il met à s'exécuter sur une liste de 10 000 valeurs.

Quel temps mettra-t-il pour s'exécuter sur une liste de 20 000 valeurs ?

  • Le même temps si le maximum est dans la première moitié de la liste.
  • On a ajouté 10 000 valeurs, l'algorithme mettra 10 000 fois plus de temps.
  • Le temps sera simplement doublé.
  • On ne peut pas savoir, tout dépend de l'endroit où est le maximum.
 Réponse(s) 

Pour rechercher le maximum, il faut systématiquement parcourir toute la liste. Si elle est deux fois plus longue, il faut deux fois plus de temps.