Comparaisons moyennes d’une recherche linéaire

Selon l’hypothèse classique où la cible peut occuper chaque position avec la même probabilité, il fournit le nombre attendu de comparaisons et le pire cas. Développeurs, étudiants et réviseurs peuvent ainsi relier la notation O(n) aux nombres concrets obtenus pour une taille de collection donnée.

Comprenez le modèle probabiliste de la moyenne

La recherche linéaire examine les éléments dans l’ordre et s’arrête dès qu’elle trouve la cible. Si une cible présente a la même probabilité d’occuper chacune des n positions, trouver le premier élément coûte une comparaison, trouver le deuxième en coûte deux et trouver le dernier en coûte n. Chacun de ces coûts a une probabilité de 1/n. Le coût attendu est donc la moyenne arithmétique des entiers de 1 à n, soit (n + 1) / 2 après simplification. Saisissez la taille de la collection dans n pour appliquer exactement cette formule. Cette hypothèse est essentielle : il ne s’agit pas d’une estimation fondée sur des mesures de durée, du matériel ou un langage de programmation. Le résultat est un décompte déterministe pour une recherche réussie avec distribution uniforme des positions. Si certaines positions ou valeurs sont recherchées plus souvent, leurs probabilités doivent être pondérées séparément. Le modèle ne couvre pas non plus une cible absente, qui impose d’examiner les n éléments.

Interprétez la moyenne et le pire cas

Le résultat moyen peut être entier ou comporter un demi. Par exemple, une collection de 100 éléments produit un coût attendu de 50.5 comparaisons. Cette fraction ne signifie pas qu’une exécution réalise une demi-comparaison : elle représente la moyenne à long terme de nombreuses recherches réussies dont les positions sont uniformément distribuées. Le pire cas vaut n, car une cible placée en dernière position n’est trouvée qu’après la vérification de tous les éléments. Pour une collection d’un élément, les deux valeurs valent un. Lorsque n augmente, la moyenne se rapproche de la moitié de la taille, tandis que le pire cas reste égal à la taille complète. Les deux grandeurs augmentent linéairement, d’où la classe O(n) pour une recherche linéaire réussie malgré des constantes différentes. Utilisez la moyenne pour une charge conforme à la distribution indiquée et le pire cas comme limite stricte d’une requête réussie. Ces nombres excluent la gestion de boucle, les accès mémoire, le tri et le coût interne d’une comparaison.

Exploitez le résultat pour la conception et les performances

Des nombres de comparaisons précis rendent les discussions algorithmiques plus utiles que la seule notation asymptotique. Vous pouvez confronter le travail attendu d’une recherche linéaire au coût de construction d’une autre structure de données, notamment lorsque la collection est petite, rarement interrogée ou souvent modifiée. Une table de hachage ou un index trié peut accélérer les consultations, mais sa création et son entretien ont un coût qu’un simple parcours évite. Ce calculateur quantifie le parcours sans prétendre mesurer la durée d’exécution. Il permet également de vérifier un exercice, de valider un modèle de feuille de calcul, de documenter une revue de code ou de produire des valeurs stables pour un cours. Conservez les conditions avec le résultat : la cible est présente, chaque position est équiprobable, la recherche part du premier élément et s’arrête à la première correspondance. Les doublons peuvent invalider ce modèle. Pour une cible absente, comptez n comparaisons ; pour des accès non uniformes, calculez une espérance pondérée.