Impatto sull'ordine degli elementi sul costo della ricerca in un elenco collegato

Question

Ho la seguente domanda a casa con cui sto lottando. Ho letto il capitolo corrispondente del libro, ma nessuna guida lì.

Considera un elenco collegato $ x: x_1 a x_2 a x_3 ldots $. Supponiamo che il costo dell'esame di un particolare elemento $ x_i $ sia $ c_i $. Si noti che per esaminare $ x_i $, è necessario scansionare tutti gli elementi di fronte a $ x_i $. Sia $ p_i $ la probabilità di cercare l'elemento $ x_i $, quindi il costo totale per tutte le ricerche è $$ sum_ {j = 1}^{n} Left (p_j CDot sum_ {i = 1}^ {j} c_i a destra) $$

1. Mostra che l'archiviazione di elementi in ordine non crescente di $ p_i/c_i $ non minimizza necessariamente il costo totale.

2. Mostra che la memorizzazione di elementi in ordine non decrescente di $ p_i $ non minimizza necessariamente il costo totale.

Qualsiasi aiuto e direzione su come affrontare il problema sarà molto apprezzato.