2
Pour la recherche binaire, quel est le nombre moyen de comparaisons nécessaires pour trouver un enregistrement dans un fichier?recherche binaire question
A
Répondre
2
Je suppose que c'est devoirs, donc je vais fournir un indice au lieu d'une réponse directe. Je supposerai aussi que l'on vous a demandé de trouver une réponse relativement exacte, pas seulement une grosse réponse O. Pensez-y de cette façon: Chaque fois que vous faites une comparaison, vous divisez par deux l'espace de recherche. Si l'espace de recherche est de taille S, la probabilité de trouver l'enregistrement à l'itération suivante est de 1/S. Si C désigne le nombre de comparaisons, alors P (le trouver sur la comparaison C) = P (ne le trouve pas dans < C comparaisons) * P (le trouver sur la comparaison C | ne le trouve pas dans < C comparaisons).
+0
Merci, une réponse big-O est dénuée de sens. Je pense que votre réponse ne va pas aider parce que c'est une question de probabilité. Je n'ai pas besoin de la probabilité que j'ai besoin du numéro. – neuromancer
+0
Mais comment calculeriez-vous la moyenne sans utiliser la probabilité? La moyenne est juste la somme de toutes les valeurs possibles de C, pondérées par leur probabilité. Cela dit, je n'ai pas complètement calculé les maths mais je peux dire que ce serait assez compliqué si je le faisais. C'est un très mauvais problème, surtout si votre professeur est un stickler pour les dérivations exactes par opposition aux approximations. – dsimcha
+2
Aussi, mon intuition est que vous avez mal compris le problème et vous devriez demander des éclaircissements. Savoir si vous avez vraiment besoin d'une réponse ** exacte **, et si non, si elle doit seulement être asymptotiquement correcte ou correcte pour chaque N. Si elle doit être exacte pour chaque N, elle est si horriblement désordonnée qu'elle est virtuellement impossible. – dsimcha
Est-ce que c'est un devoir? – dsimcha
C'est lié aux devoirs. Et alors? – neuromancer
Donc, si le but était que vous le découvriez vous-même, personne ici ne veut vous aider à tricher. – Cascabel