Impacto en el orden de elementos en el costo de búsqueda en una lista vinculada

Question

Tengo la siguiente pregunta de tarea con la que estoy luchando. He leído el capítulo correspondiente del libro, pero no hay orientación allí.

Considere una lista vinculada $ x: x_1 a x_2 a x_3 ldots $. Suponga que el costo de examinar un elemento particular $ x_i $ es $ c_i $. Tenga en cuenta que para examinar $ x_i $, uno necesita escanear a través de todos los elementos frente a $ x_i $. Sea $ p_i $ la probabilidad de buscar elemento $ x_i $, por lo que el costo total para todas las búsquedas es $$ sum_ {j = 1}^{n} izquierda (p_j cdot sum_ {i = 1}^ {j} c_i right) $$

1. Demuestre que almacenar elementos en orden no creciente de $ P_I/C_I $ no necesariamente minimiza el costo total.

2. Demuestre que almacenar elementos en orden de no depósito de $ P_i $ no necesariamente minimiza el costo total.

Cualquier ayuda y dirección sobre cómo abordar el problema será muy apreciado.