El objetivo de este documento es condensar los aspectos más importantes de algoritmos y estructuras de datos, fundamentales para afrontar las entrevistas técnicas de desarrollador software. Este repositorio es un fork de un repositorio originalmente en Inglés, del que he modificado algunas cosas y añadido otras, dando una visión más completa sobre estos temas con consejos muy útiles.
Antes de entrar a analizar y comparar los algoritmos, debemos tener una manera de medir su rendimiento independientemente de la máquina o lenguaje en los que los ejecutemos/implementemos. De esta necesidad surge la notación Big O (Og(x)), que nos sirve para representar la cantidad de recursos computacionales o temporales necesarios para resolver un problema. En resumen, la notación Big O nos dirá cuánta memoria o tiempo necesita un algoritmo para resolver un problema dada una input.
Los diferentes órdenes más habituales son los siguientes, ordenados de mejor a peor:
- Constante -
O(1)El coste (temporal o espacial) es constante independientemente de la input. - Logaritmico –
O(log n)El coste crece de manera logaritmica conn. - Lineal –
O(n)El coste crece de manera lineal conn. - Lineal logaritmica –
O(n log n)El coste crece de manera más rápida que en el caso linealn. - Exponencial –
O(c^n)El coste crece de manera exponencial conn. - Factorial –
O(n!)El coste crece de manera factorial, haciendo que sea casi imposible de ejecutar hasta para pequeños valores den.
En esta gráfica podemos observar la diferencia entre los órdenes mencionados, relancionando la input con el número de pasos que nos llevará el problema:
(source: Wikipedia, Computational Complexity of Mathematical Operations)
- La notación Big O no implica que se esté analizando el peor escenario posible, sólo nos dice cómo será su rendimiento dado un escenario en particular, asegurándonos cómo se comportará según el valor de
n(elementos) de la input vaya creciendo. - Los escenarios más útiles para analizar con el peor caso posible, en el que la input será lo menos adecuada posible, y el caso estándar en el que la input será lo que nos encontraremos habitualmente.
- No se utiliza el mejor caso posible ya que no nos orienta hacia el rendimiento real del algoritmo.
- Almancena elementos de un sólo tipo (String, Object, int...) con la ayuda de un índice secuencial.
- Son una estructura fija, una vez creados podremos modificar su contenido, pero no su longitud.
- Un array es almacenado como un bloque contiguo en memoria, en el que cada elemento ocupa el mismo espacio.
- Si conocemos el índice de un elemento del array, el tiempo para acceder a él será siempre
O(1), independientemente de cuál sea el valor de ese índice. - Si no conocemos el índice de un elemento del array, la complejidad de la operación que queramos hacer con ese elemento será de
O(n). - Existe un tipo especial de Arrays, los Arrays Dinámicos, que nos permiten variar su tamaño en tiempo de ejecución. Si se queda sin espacio para añadir elementos, copia su contenido a otro array dinámico más grande.
- Los arrays pueden tener más de una dimensión, permitiéndonos crear matrices.
TBD
TBD
TBD
Un algoritmo es un conjunto de instrucciones o reglas definidas y no ambiguas, ordenadas y finitas, que permite solucionar un problema. Dados un estado inicial y una entrada de datos, obtendremos la salida o el resultado, que será la solución al problema.
- Un algoritmo que se caracteriza por repetir una secuencia n veces.
- Usados habitualmente para recorrer un conjunto de datos.
- Pueden ser implementados recursivamente, lo que suele mejorar su comprensión y reducir el código necesario.
- Un algoritmo que se llama a sí mismo en su definición.
- Caso Base: Estos algoritmos poseen un caso que rompe la recursividad y devuelve una respuesta.
- Un algoritmo que mantiene el orden de aparición de los elementos repetidos.
- Un algoritmo que no mantiene el orden de aparición de los elementos repetidos.
- Un algoritmo que mantiene el orden de aparición de los elementos repetidos.
Stack overflow. Si este error aparece en tiempo de ejecución, es que han podido suceder dos cosas:
- No has alcanzado el caso base ya que el problema es tan grande que no dispones de más memoria, con lo cuál habría que buscar alguna alternativa.
- No has alcanzado el caso base ya que tu algoritmo está mal definido. Esto es fundamental y hay que tener muy claras las condiciones que rompen la recursividad, y saber si se cumplen en algún momento o estamos haciendo algo mal.
TBD
TBD
- Este algoritmo recorre el array iterativamente de izquierda a derecha comparando elementos adyacentes e intercambiádolos de posición si el de la izquierda es mayor que el de la derecha.
- Divide el array de manera lógica en una parte desordenada y otra ordenada. En la parte ordenada se va colocando uno a uno el elemento mayor de la parte desordenada gracias a los intercambios de elementos de las iteraciones.
- La parte ordenada irá creciendo de derecha a izquierda, hasta acabar con el array completamente ordenado.
- No vuelve a iterar por la parte ordenada.
- Algoritmo In Situ.
- Estable (elementos del mismo valor mantendrán el orden de aparición).
- Su rendimiento degrada muy rápido con arrays grandes.
- Caso Estándar:
O(n^2) - Caso Peor:
O(n^2)
- Caso Peor:
O(1)
(source: Wikipedia, Insertion Sort)
- Este algoritmo recorre el array iterativamente de izquierda a derecha, comparando los elementos de la parte desordenada buscando el mayor de ellos, que será colocado en la parte ordenada una vez acabemos la iteración, intercambiándolo por el de la posición que va a ocupar.
- La parte ordenada irá creciendo de derecha a izquierda, hasta acabar con el array completamente ordenado.
- Sólo se realiza el intercambio cuando se ha recorrido toda la parte desordenada del array.
- Algoritmo In-place.
- No estable.
- No es eficiente para arrays grandes.
- Caso Estándar:
O(n^2) - Caso Peor:
O(n^2)
- Worst Case:
O(1)
(source: Wikipedia, Selection Sort)
- Este algoritmo recorre el array de izquierda a derecha, comparando los elementos de la parte desordenada con el elemento a ordenar de derecha a izquierda, y si son mayores que este, desplaza su posición en 1 hacia la derecha. Este proceso se repite hasta encontrar la posición correcta para el elemento.
- La parte ordenada irá creciendo de izquierda a derecha.
- No vuelve a iterar por la parte ordenada.
- Algoritmo In-place.
- Estable.
- No eficiente para arrays grandes, aunque puede ser más rápido que otros algoritmos para arrays pequeños.
- Más eficiente que burbuja ya que realiza menos intercambios.
- Caso Estándar:
O(n^2) - Caso Peor:
O(n^2)
- Caso Peor:
O(1)
(source: Wikipedia, Insertion Sort)
- Algoritmo basado en el paradigma divide y vencerás.
- Divide recursivamente el array a la mitad, creando dos arrays auxiliares, hasta que sean de un solo elemento, llegando al caso base.
- Cuando alcanzamos el caso base, se devuelven los resultados ordenados ascendiendo desde la izquierda a la derecha.
- Las llamadas recursivas van obtienendo los arrays ordenados, que van doblando su tamaño hasta que el array entero está ordenado.
- NO es un algoritmo In-place.
- Estable.
- Caso Estándar:
O(n log n) - Caso Peor:
O(n log n)
- Caso Peor:
O(n)
(source: Wikipedia, Merge Sort)
- Algoritmo basado en el paradigma divide y vencerás.
- Divide el array en dos partes con la ayuda de un pivote, situando a la izquierda los valores menores que este y a la derecha los valores mayores que este.
- La selección más común para este pivote suele ser el primer elemento del array.
- Cuando termine de reordenar los elementos en torno al pivote, este se encontrará en su posición final.
- Repite este proceso para la parte derecha e izquierda del pivote, hasta que compare sólo dos elementos, lo que significa que el array estará ordenado.
- Cuando el lado izquierdo del pivote esté ordenado, se ordena el lado derecho.
- Algoritmo In-place.
- No estable.
- Aunque tenga la misma Big O (o algo peor) que otros algoritmos de ordenación de arrays, en la práctica es más rápida que otros algoritmos (como por ejemplo Merge Sort).
- Otra de sus ventajas es la complejidad espacial frente a Merge Sort.
- Caso Estándar:
O(n log n) - Caso Peor:
O(n^2)
- Caso Peor:
O(log n)
(source: Wikipedia, Quicksort)
TBD
TBD
TBD
TBD