Impacto en el orden de elementos en el costo de búsqueda en una lista vinculada
-
31-10-2019 - |
Pregunta
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) $$
Demuestre que almacenar elementos en orden no creciente de $ P_I/C_I $ no necesariamente minimiza el costo total.
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.
No hay solución correcta