El análisis de algoritmos es necesario porque cada algoritmo tiene comportamientos diferentes. Para seleccionar el algoritmo correcto, necesita saber cuáles son esos comportamientos.
El ejemplo más clásico es la clasificación.
Bubble Sort es la forma más “obvia” de ordenar una lista. Se desplaza por la lista mirando pares de elementos individuales y los intercambia si están en el orden incorrecto. Si lo hace una vez, la lista no estará en orden, pero si lo hace suficientes veces, la lista finalmente se ordenará por completo.
- ¿Cómo se mejora un algoritmo de aprendizaje automático basado en la experiencia?
- Si existen múltiples rutas más cortas entre 2 nodos en un gráfico no dirigido, ¿es posible imprimirlas todas utilizando el algoritmo de Dijkstra?
- ¿Cuáles son algunos algoritmos interesantes que se han encontrado en la naturaleza?
- ¿Qué es el algoritmo TDIDT?
- ¿Cuál es el valor de la suma k ^ 2 * C (n, k) 0 a n?
Lamentablemente, también puede llevar mucho tiempo. En el peor de los casos, debe iterar sobre la lista de tamaño N N veces, denominada O (N ^ 2).
En una lista de 10 elementos no es gran cosa, pero en 10,000,000 de elementos no es razonable.
Merge Sort es un algoritmo más complejo. No es tan obvio, pero los beneficios se vuelven claros muy rápidamente.
La ordenación por fusión es un algoritmo recursivo. Divide la lista por la mitad y ejecuta merge-sort en cada mitad. Al repetir este proceso de división, finalmente tiene listas de tamaño 1, que obviamente ya están ordenadas, ¡fácil!
Luego, una vez que ambas sublistas están ordenadas, combina el resultado. Debido a que sabe que ambas listas están en orden, solo necesita pasar por encima de cada sublista una vez para hacerlo; nunca necesita profundizar para buscar valores fuera de orden
El tiempo de ejecución absoluto en el peor de los casos de este algoritmo es O (N log N). En una lista grande, esto es mucho más rápido.
¿Pero qué hay de la RAM?
Aquí es donde creo que la importancia es realmente llevada a casa.
La clasificación de burbujas se puede hacer fácilmente en el lugar usando solo una variable para mantener los valores mientras cambias sus posiciones. La pila de métodos del software también es muy razonable: puede implementar esto como un bucle muy simple.
El tipo de fusión es un poco más complejo. Las implementaciones más comunes usan múltiples matrices más pequeñas para reorganizar los datos, lo que requiere memoria 2N. Además, debido a que es un método recursivo, la pila de tiempo de ejecución se usa mucho más.
Entonces, ¿cuál usas?
Dígame usted.
Si tiene una lista de 10,000,000 de elementos, con mucha RAM disponible, ¿cuál seleccionaría? Combinar tipo, naturalmente.
Si tiene una lista de 1,000 elementos, pero tiene RAM extremadamente limitada, ¿cuál seleccionaría? Tipo de burbuja, a pesar de lo “malo” que sea.
Debido a que analizamos cómo se comporta cada uno de los algoritmos, podemos tomar una decisión inteligente en función de nuestras necesidades.
( Nota: en realidad hay otros algoritmos de ordenamiento que son una mejor opción que el ordenamiento por burbujas en ese caso, pero este es un ejemplo simplificado )
