Saltar al contenido ForoHackers

Estructuras de datos: por dónde empezar

Estructuras de datos
#3398 · · Citar · Denunciar

Una estructura de datos es una forma de organizar los datos en memoria para que las operaciones que necesitas sean baratas. Arreglos, listas, tablas hash y árboles guardan los mismos elementos; se distinguen en lo rápido que los encuentran, insertan, borran u ordenan. Elegir bien suele importar más que cualquier microoptimización.

Conceptos clave

  • Tipo abstracto de datos e implementación: una pila o un mapa es una interfaz; los arreglos o los nodos enlazados son maneras de construirla.
  • Memoria contigua o enlazada: los arreglos aprovechan la caché y se indexan en tiempo constante; los nodos enlazados insertan barato pero obligan a seguir punteros.
  • Hashing: una función hash lleva una clave a una posición; las colisiones se resuelven con encadenamiento o sondeo.
  • Árboles balanceados: mantener un árbol de búsqueda poco profundo da búsqueda, inserción y borrado logarítmicos.
  • Montículos y colas de prioridad: acceso rápido al elemento menor o mayor.

Vocabulario

  • Coste amortizado: el coste medio por operación en una secuencia larga, como cuando un arreglo dinámico se duplica.
  • Factor de carga: la razón entre los elementos guardados y las posiciones de una tabla hash.
  • Invariante: una propiedad que la estructura mantiene tras cada operación, como el orden del montículo.
  • Estructura persistente: la que conserva disponibles las versiones antiguas tras una actualización.

Qué estudiar, en orden

  1. Construye un arreglo dinámico y una lista enlazada simple; mide el tiempo de insertar al principio y al final.
  2. Implementa una tabla hash con encadenamiento, luego redimensiónala y observa el factor de carga.
  3. Implementa un árbol binario de búsqueda y después una variante balanceada, como un AVL o un rojo-negro.
  4. Construye un montículo binario y úsalo para una cola de prioridad y para heapsort.
  5. Mira los conjuntos disjuntos, los tries y los árboles B, y pregúntate qué hace rápido cada uno.

Etiquetas relacionadas

#algorithms #memory-management #databases #complexity

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder