Algoritmos 101 básicos
Cuando empezamos en programación lo primero que aprendemos son algoritmos por lo general muy simples y aunque en ese momento
Estemos pendiente de como se muestra un botón o de las últimas tendencias en el framework de turno (ya hablaremos sobre frameworks) es un tipo de conocimiento que debemos llevar hasta el límite.
>”Lo que diferencia a los maestros de los amateurs es el dominio inigualable de los fundamentos”
Si querés entrar a una empresa del big four (Google, Facebook, Amazon, Microsoft) te van a pedir un profundo conocimiento de algoritmos y no es porque sean fancys o les guste que sepas resolver problemas raros sino que al ser desarrollos de alto tráfico y de alta disponibilidad no se pueden dar el lujo de que un proceso tome mucho tiempo en ejecutarse o consuma demasiados recursos.
El problema que tenés acá es el siguiente: ¿qué va a pasar cuando tengas requerimientos muy específicos?, o que te rechacen el feature por 7 milisegundos demás por request y todo lo que encontras en internet son ciclos anidados o cosas así, que la gente con la mejor de las voluntades intentan ayudarte pero el único responsable de ganar esa contienda sos vos.
Todo lo que tenés que hacer para salirte con la tuya ante ese reto es recordar tus lecciones con el viejo sabio sobre algoritmos.
Si no sabes que es un Algoritmo estas en el lugar indicado porque voy a explicarte como viene la mano.
Qué es un algoritmo?
Un algoritmo es un conjunto de operaciones o instrucciones que te permiten encontrar la solución a un problema. Cualquiera sea la índole, puede ser prepararte un café, salir de tu casa u ordenar un conjunto de números enteros de menor a mayor.
Definir la serie de pasos a seguir para cumplir nuestro cometido es nuestra tarea a la hora de sentarnos a diseñar un algoritmo.
Hasta ahora venimos bien, cualquiera puede diseñar un algoritmo, ahora demosle una breve dosis de realidad. El algoritmo además de existir tiene que resolver de manera eficiente, no basta con que solo resuelva el problema.
Como saber que tan eficiente es un algoritmo?
Ya escribimos un programa que resuelve algo, ahora quiero saber como medir su eficiencia:
– Cantidad de líneas de codigo? NO
– Cantidad de tiempo que tarda en ejecutarse? NO.
La cantidad de líneas de código no afecta en nada al rendimiento de un programa y la cantidad de tiempo de ejecución está muy ligada a la computadora que se use para ejecutar el programa, no es lo mismo probar un software en una PC de los 90 que en una actual.
Normalmente se usa la notación “Big O” en la cual se asumen constantes como cantidad de instrucciones máquina y media de intrucciones máquina que ejecuta una computadora específica.
Hay mucha teoría para digerir acerca de como deducir el Orden de una función y no me voy a adentrar en esas oscuras aguas, de momento me voy a limitar a enumerar Órdenes comunes
– O(1) -> var a = arr[3]
– O(log n) -> Dividir el problema en 2 hasta encontrar la solución
for(var i = 100; i > 0; i/=2){console.log(i)}
– O(n) -> Como máximo se ejecutará n veces
var a = 9
var n = 10
for (var i = 0; i<n; i++){
if (i === a){
console.log(‘YEAH LO ENCONTRÉ’)
}
}
– O(n log n) -> Una instrucción de Órden O(log n) dentro de una O(n)
– O(n^2) -> Una instrucción de Órden O(n) dentro de otra de Órden(n)
var n = 100
for (var i=n; i<=n; i++){
for (var j=n; j<=n; j++>){
console.log(i, j)
}
}
– Y hay casos mas extremos como O(n^3), O(2^n), O(n^n), O(n!) pero los voy a desestimar por ser de uso muy limitado
Hay algo que me gustaría aclarar “Si sabemos que van a ser pocos datos y eso NUNCA VA A CAMBIAR, da igual el orden del algoritmo que usemos”.
Paradigmas
Fuerza bruta
Consiste en enumerar todas las posibles soluciones de un problema .
Voraz (Greedy)
Se elige la solución óptima actual sin considerar nada a futuro.
Divide y vencerás
Dividir el problema en partes más pequeñas hasta encontrar la solución.
Programación dinamica
Se divide el problema en subproblemas más pequeños y se usa el resultado de estos subproblemas para resolver el problema principal, por ejemplo una función recursiva.
Búsqueda hacia atrás (Backtraking)
Es parecido a Fuerza Bruta, intenta generar todas las soluciones posibles y cada vez que generas una nueva solución preguntás si satisface todas las condiciones, solo en caso
de ser cierto sigue generando soluciones subsecuentes. Sino vuelve atrás e intenta en un camino diferente.
Ramificación y poda (Branch and Bound)
Similar al Backtracking solo que se fija si las condiciones no son óptimas deja de adentrarse en los subnodos, vuelve atras e intenta por otro camino.
El conocimiento sobre algoritmos te va a dar la capacidad de resolver Tipos de problemas de una manera eficiente y te va a hacer un mejor desarrollador
Si querés que publique más artículos con ejemplo hacémelo saber
<El último apaga la luz>