Impact sur l'ordre des éléments sur le coût de la recherche dans une liste liée

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) $$

1. 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.

2. 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.