Estructuras de datos y algoritmos (DSA)

Big O describe cómo crecen el tiempo o el espacio que necesita un algoritmo a medida que aumenta el tamaño de la entrada. Al analizarlo, identifica el tamaño de entrada, cuenta las operaciones dominantes y expresa el crecimiento asintótico; normalmente se omiten constantes y términos de menor orden. Por ejemplo, recorrer un arreglo toma O(n), y comparar cada par de elementos suele tomar O(n²).

Aclara si hablas del caso peor, promedio o mejor, y distingue el espacio total del espacio auxiliar. En una entrevista también conviene explicar los supuestos: una búsqueda en una tabla hash suele ser O(1) en promedio, pero puede llegar a O(n) en el peor caso.

Un arreglo dinámico ofrece acceso por índice O(1) y buena localidad de memoria. Agregar al final cuesta O(1) amortizado, aunque una expansión ocasional copia sus elementos y cuesta O(n). Insertar o borrar en medio normalmente requiere desplazar elementos y también cuesta O(n).

Una lista enlazada permite insertar o quitar un nodo en O(1) si ya tienes su referencia, pero encontrar la posición requiere recorrerla en O(n) y el acceso por índice es O(n). Explica las operaciones que predominan y las restricciones de memoria antes de elegir.

Una tabla hash transforma una clave en un índice para consultar, insertar o borrar valores en O(1) esperado. Dos claves pueden producir el mismo índice: la tabla resuelve esas colisiones, por ejemplo, guardando varios elementos en un mismo espacio o buscando otra posición disponible.

Si las colisiones se acumulan, las operaciones pueden degradarse hasta O(n). Un factor de carga controlado y el redimensionamiento ayudan a conservar el rendimiento promedio. Las claves también deben mantener coherencia entre igualdad y hash: si dos claves son iguales, deben producir el mismo hash.

Una pila sigue el orden último en entrar, primero en salir (LIFO); sus operaciones típicas son insertar y quitar en la cima. Sirve, por ejemplo, para deshacer acciones, evaluar expresiones y recorrer con retroceso.

Una cola sigue el orden primero en entrar, primero en salir (FIFO), con inserciones al final y extracciones al inicio. Una cola de doble extremo permite insertar y quitar por ambos extremos. En una entrevista, relaciona la estructura con el orden de procesamiento que necesita el problema.

En una secuencia ordenada, compara el elemento del medio con el objetivo y descarta la mitad que ya no puede contenerlo. El tiempo es O(log n); si se trabaja sobre un arreglo, el espacio auxiliar puede ser O(1) con una versión iterativa.

Define primero el intervalo de búsqueda y mantén el mismo criterio al actualizar sus límites. Decide si necesitas cualquier coincidencia, la primera posición válida o la posición de inserción. Las variantes de “primera posición que cumple una condición” funcionan cuando esa condición es monótona: pasa de falsa a verdadera, o al revés, una sola vez.

En un árbol de búsqueda binaria, los valores de cada subárbol respetan el orden definido respecto de su nodo. Una búsqueda, inserción o eliminación cuesta O(h), donde h es la altura: O(log n) si el árbol está balanceado, pero O(n) si se convierte en una cadena.

El recorrido inorden visita las claves en orden. Los árboles balanceados, como los AVL o los rojo-negro, limitan la altura mediante reglas de balanceo, a cambio de trabajo adicional durante las actualizaciones.

BFS explora el grafo por capas y encuentra caminos con el menor número de aristas en un grafo no ponderado. DFS explora una rama hasta donde puede antes de retroceder; es útil para detectar ciclos, recorrer componentes y procesar dependencias.

Con listas de adyacencia, ambas búsquedas toman O(V + E), donde V es el número de vértices y E el de aristas. Marca los vértices al descubrirlos para no procesarlos repetidamente. Para grafos ponderados, BFS no basta para hallar el camino de menor costo en general.

Un heap binario es un árbol casi completo que mantiene su mínimo o máximo en la raíz. Consultar la raíz cuesta O(1), insertar y extraer el extremo cuestan O(log n), y construir el heap a partir de n elementos puede hacerse en O(n).

Una cola de prioridad es útil cuando siempre debes procesar el elemento de mayor o menor prioridad, por ejemplo, para obtener los k elementos más grandes o elegir el siguiente vértice en Dijkstra. No mantiene todos los elementos completamente ordenados.

Un ordenamiento estable conserva el orden relativo de elementos que tienen la misma clave. Eso permite ordenar por varios criterios de forma sucesiva sin perder el orden de un criterio anterior. Por ejemplo, ordenar registros por fecha y luego de manera estable por categoría conserva el orden por fecha dentro de cada categoría.

Los algoritmos de comparación tienen un límite inferior de Ω(n log n) comparaciones en el caso general. Counting sort y radix sort pueden mejorar ese crecimiento cuando las claves tienen un rango o representación que permite aprovechar supuestos adicionales.

Un algoritmo voraz toma la decisión local que parece mejor en cada paso y normalmente no la cambia. Es correcto solo cuando se puede justificar que esas decisiones conducen a una solución global óptima; el argumento suele apoyarse en una propiedad de elección voraz o un intercambio.

La programación dinámica se aplica cuando subproblemas se repiten y sus resultados ayudan a resolver problemas mayores. Define el estado, la transición y los casos base; después calcula cada subproblema una vez, mediante memoización o tabulación. Explica cuántos estados hay y cuánto cuesta cada transición para obtener la complejidad.

Úsala para construir soluciones de forma incremental cuando una decisión parcial puede llevar a una solución completa o descartarse. Define un caso base, elige una opción, explora sus consecuencias y deshaz la elección antes de probar la siguiente. Sirve para permutaciones, combinaciones, Sudoku y búsqueda en laberintos.

En el peor caso puede explorar un espacio exponencial. Reduce trabajo descartando temprano ramas que violen las restricciones; si estados distintos alcanzan el mismo subproblema, considera memoización o programación dinámica.

Dos punteros avanzan por una secuencia para buscar una relación entre elementos, por ejemplo, un par con suma objetivo en un arreglo ordenado. La ventana deslizante mantiene un intervalo contiguo y actualiza su estado al mover uno o ambos límites; suele encontrar el subarreglo más largo o más corto que cumple una condición.

Ambas técnicas pueden reducir una solución de O(n²) a O(n) cuando cada puntero avanza como máximo n veces. Antes de aplicarlas, comprueba la propiedad que permite descartar elementos; por ejemplo, una ventana basada en suma positiva no se comporta igual si también hay valores negativos.

Una suma de prefijos almacena acumulados desde el inicio. Con ella, la suma de un intervalo puede calcularse en O(1) después de un preprocesamiento O(n), y también se pueden contar subarreglos con una suma objetivo usando una tabla de frecuencias.

Para muchas actualizaciones de rango, una matriz de diferencias registra cómo cambia el valor en los extremos y luego reconstruye el resultado con un recorrido. Aclara si los intervalos incluyen ambos extremos para evitar errores de uno en los límites.

Es una pila cuyos elementos se mantienen en orden creciente o decreciente según el problema. Al llegar un valor que rompe ese orden, se retiran elementos que ya no pueden ser la respuesta. Así se encuentran, por ejemplo, el siguiente valor mayor o el área de un histograma en O(n) amortizado: cada elemento entra y sale como máximo una vez.

Una cola monótona aplica una idea similar a una ventana móvil y conserva candidatos útiles para obtener el mínimo o máximo de cada ventana en tiempo lineal.

Un trie guarda claves por prefijos compartidos, normalmente un carácter por arista. Buscar, insertar o eliminar una palabra de longitud L toma O(L), sin depender directamente del número de palabras almacenadas.

Es útil para autocompletado, diccionarios y búsquedas por prefijo. Puede consumir mucha memoria si cada nodo reserva espacio para muchas transiciones; compara una representación dispersa o compacta y considera si las consultas por prefijo justifican ese costo.

Disjoint Set Union (DSU), también llamado Union-Find, mantiene una colección de componentes disjuntos. La operación find identifica el representante de un elemento y union combina dos componentes. Compresión de caminos y unión por tamaño o rango hacen que una secuencia de operaciones tenga costo amortizado casi constante.

Se usa para detectar si una arista conecta dos componentes ya unidos, como en Kruskal, o para agrupar elementos relacionados. No mantiene por sí solo las aristas ni permite contestar consultas de camino entre vértices.

Es un orden lineal de los vértices de un grafo dirigido en el que cada arista va de un vértice anterior a uno posterior. Existe solo si el grafo es acíclico (DAG). Puede calcularse quitando repetidamente vértices de grado de entrada cero o mediante DFS; ambas estrategias toman O(V + E) con listas de adyacencia.

Se aplica a dependencias de tareas, módulos o cursos. Si al terminar quedan vértices sin procesar, hay un ciclo y no existe un orden topológico que las satisfaga a todas.

BFS encuentra caminos de menor número de aristas cuando todas las aristas tienen el mismo costo. Dijkstra maneja pesos no negativos y, con una cola de prioridad y listas de adyacencia, suele tomar O((V + E) log V). Bellman-Ford admite pesos negativos y puede detectar ciclos negativos alcanzables, con un costo mayor de O(VE).

Elige según las propiedades del grafo y aclara qué significa “menor”: menos saltos o menor suma de pesos. Un ciclo negativo que se pueda alcanzar y luego usar para llegar al destino hace que el costo mínimo no esté acotado.

En un grafo no dirigido, conecta todos los vértices con costo total mínimo y sin ciclos. Kruskal ordena las aristas y agrega las que conectan componentes distintos, normalmente usando Union-Find. Prim amplía un árbol actual con la arista más barata que cruza hacia otro vértice.

Ambos algoritmos suelen implementarse en O(E log V) u O(E log E), según la representación y la cola de prioridad. Un árbol de expansión mínima no necesariamente contiene el camino más corto entre cada par de vértices.

Merge sort garantiza O(n log n), es estable en su forma habitual y requiere espacio adicional lineal para arreglos. Quicksort suele ser rápido en la práctica y usa poco espacio adicional con partición in situ, pero puede degradarse a O(n²) con pivotes desfavorables; la selección aleatoria o introsort reducen ese riesgo.

Heapsort garantiza O(n log n) y puede ordenarse in situ, aunque no es estable y suele tener peor localidad de memoria. Elige según garantías, estabilidad y memoria, no solo según el mejor caso.

Si k es pequeño frente a n, un min-heap de tamaño k mantiene los mejores candidatos en O(n log k) tiempo y O(k) espacio. También puedes ordenar todo en O(n log n) si después necesitas el orden completo.

Quickselect particiona alrededor de un pivote y coloca el k-ésimo elemento sin ordenar la colección entera. Su costo esperado es O(n), aunque el peor caso puede ser O(n²); considera una estrategia de pivote que limite ese riesgo cuando importen garantías.

Convierte los extremos de intervalos en eventos ordenados y recorre esos eventos manteniendo el estado activo. Así se detectan solapamientos, se combinan intervalos o se cuenta cuántas salas se necesitan para reuniones. Ordenar suele dominar el costo, por lo que el tiempo es O(n log n).

Define si un intervalo es cerrado o abierto y qué evento debe procesarse primero cuando dos extremos coinciden. Esa convención cambia resultados en los límites y es una fuente común de errores.

Explica por qué produce una respuesta válida para toda entrada permitida, no solo para los ejemplos. En un bucle puedes formular una invariante: algo que es verdadero antes de empezar, se conserva en cada iteración y, al terminar, permite concluir el resultado.

En una solución recursiva, prueba que los casos base son correctos y que cada paso reduce el problema a instancias menores cuya respuesta correcta permite construir la solución. Si existe una estrategia voraz, justifica también por qué una decisión local no elimina todas las soluciones óptimas.

Identifica cuántos subproblemas de tamaño aproximado n/b genera cada nivel y cuánto cuesta dividir y combinar los resultados. Expresa el tiempo como una recurrencia, por ejemplo T(n) = aT(n/b) + f(n), y resuélvela con un árbol de recursión o el teorema maestro cuando sus supuestos se cumplen.

Cuenta también la profundidad de recursión y el espacio temporal de combinación. La complejidad de tiempo no incluye automáticamente la pila de llamadas ni los arreglos auxiliares.

Permiten consultar o modificar bits individuales con AND, OR, XOR, desplazamientos y máscaras. Pueden representar un conjunto pequeño de opciones, activar indicadores o comprobar propiedades como si un entero tiene un único bit en uno.

Úsalas cuando el dominio y los límites estén claros. Considera el tamaño y signo del tipo entero, la precedencia de operadores y el riesgo de desbordamiento; una versión compacta que nadie puede revisar no es una mejora por sí sola.

Organiza la práctica alrededor de arreglos y hashing, pilas y colas, árboles y heaps, ordenamiento, grafos, búsqueda y programación dinámica. Para cada problema, explica los casos límite, justifica la corrección y calcula tiempo y espacio antes de optimizar.

Como material de referencia, consulta el programa de MIT 6.006, sus notas de algoritmos y estructuras de datos y el libro de algoritmos de Princeton.