Problemas de programación de algoritmos y estructura de datos

Ahora considere el problema de almacenar múltiples nombres de planetas (todos nombres únicos) en un directorio que pueda usarse más adelante. Para los siguientes dos casos de uso, compare y contraste matrices, árboles de búsqueda binarios, árboles avl y tablas hash utilizando funciones hash lineales, e indique cuál de los dos casos siguientes eligió para maximizar el proceso de inserción rápida.

I) Seleccione 100.000 palabras de la novela para insertar, de las cuales 10.000 palabras no están repetidas (Nota del traductor: es decir, se insertan aleatoriamente y no en orden alfabético).

Ii) Selecciona 50.000 palabras diferentes del diccionario para insertarlas, la mayoría de las cuales están ordenadas.

Solo debes preocuparte por el rendimiento de la velocidad y no considerar el rendimiento de la memoria por el momento. Como referencia, log2(10000) es aproximadamente igual a 13, log2(50000) es aproximadamente igual a 16 y log2(10000) es aproximadamente igual a 17.

Nota:

"Comparación" se refiere a analizar características similares de diferentes estructuras de datos.

"Contraste" significa discutir los diferentes significados de las diferentes estructuras de datos.

Esta pregunta no es una elección entre 1 y 2. 1 y 2 son escenarios diferentes. La primera es la inserción de información aleatoria, el 90% de los datos son innecesarios. El segundo es la inserción de información ordenada.

Esta pregunta es bastante problemática y no puedes garantizar que la respuesta sea correcta. Analicémoslo brevemente. Para la operación de inserción, existen básicamente dos procesos: "buscar" (también determina la posición de inserción) e "insertar":

1.

a, una matriz no ordenada, la complejidad del tiempo de búsqueda es O (N), la complejidad de inserción es O (1) y siempre se inserta hasta el final.

b. Ordene la matriz y utilice el método de búsqueda binaria. La complejidad del tiempo de búsqueda es O (log2 (N)). no considerado en el problema. Entonces la complejidad del tiempo es O (1).

2. El árbol de búsqueda binaria también anotó dos goles.

a, si está equilibrado, la complejidad de la búsqueda es O (log2 (N)) y la inserción es básicamente O (1).

b, desequilibrado. Aunque la complejidad de búsqueda promedio sigue siendo O (log2 (N)), en realidad es mayor que este valor en la mayoría de los casos. La inserción es básicamente O(1).

3. avl-tree, este árbol es esencialmente un árbol de búsqueda binaria, su nombre es "árbol de búsqueda binaria autoequilibrado", por lo que cualquier operación en él garantiza que esté equilibrado Árbol de búsqueda binaria, la inserción La complejidad del tiempo es como se muestra arriba.

4. Tabla hash de función hash lineal. Las tablas hash se caracterizan por unidades de recuento de depósitos preasignadas y, a menudo, utilizan un método de resolución de conflictos en el que cada unidad almacena una lista vinculada. Su rendimiento de búsqueda depende de si los datos clave de muestra se distribuyen uniformemente en la imagen de la función hash. Cuanto más uniforme sea, mayor será el efecto. La complejidad de la búsqueda y la complejidad de la inserción están determinadas por la longitud del depósito, la elección de la función hash y el método de resolución de colisiones.

Análisis combinado de los casos 1 y 2:

Caso 1: Dado que los datos insertados están desordenados y el 90% están repetidos (es decir, el rendimiento de la búsqueda es más importante que el rendimiento de inserción), obviamente, los valores de depósito y las funciones hash (incluso las funciones lineales tienen opciones), las tablas hash adecuadas y los métodos de resolución de conflictos tienen el mejor rendimiento (inclinándose hacia O (1)), seguidos de avl-tree, matrices ordenadas. y avl -árbol.

Caso 2: Los datos de entrada están ordenados, la tabla hash con los parámetros apropiados aún tiene el mejor rendimiento y la complejidad del tiempo tiende a O (1), seguida de avl-tree. La complejidad de búsqueda de matrices ordenadas también es log2 (N). Debido a que se trata de datos ordenados, cuando el orden de tamaño es consistente con el orden del diccionario, la complejidad de inserción es muy baja. Por el contrario, la complejidad de inserción es muy alta y casi todos los datos deben moverse cada vez. Los datos ordenados también hacen que los subárboles izquierdo y derecho del árbol de búsqueda binario desequilibrado estén gravemente desequilibrados, la complejidad de la búsqueda tiende a O (N) y el rendimiento es bastante bajo. Las matrices sin clasificar siguen siendo ineficientes.