Impact sur l'ordre des éléments sur le coût de la recherche dans une liste liée
-
31-10-2019 - |
Question
J'ai la question des devoirs suivants avec lesquels j'ai du mal. J'ai lu le chapitre correspondant du livre, mais aucune orientation là-bas.
Considérez une liste liée $ x: x_1 à x_2 à x_3 ldots $. Supposons que le coût d'examen d'un élément particulier $ x_i $ est $ c_i $. Notez que pour examiner $ x_i $, il faut parcourir tous les éléments devant $ x_i $. Soit $ p_i $ la probabilité de rechercher l'élément $ x_i $, donc le coût total pour toutes les recherches est $$ sum_ {j = 1} ^ {n} Left (p_j cdot sum_ {i = 1} ^ ^ {j} c_i droit) $$
Montrez que le stockage des éléments dans l'ordre non croissant de $ P_I / C_I $ ne minimise pas nécessairement le coût total.
Montrez que le stockage des éléments par ordre non décroissant de $ P_i $ ne minimise pas nécessairement le coût total.
Toute aide et direction sur la façon d'approcher le problème seront très appréciées.
Pas de solution correcte