Todo buen desarrollador tiene tiempo en mente. Quieren darles a sus usuarios más, para que puedan hacer todas esas cosas que disfrutan. Hacen esto minimizando la complejidad del tiempo .
Antes de que pueda comprender la complejidad del tiempo en la programación, debe comprender dónde se aplica más comúnmente: en el diseño de algoritmos .
Entonces, ¿qué es un algoritmo?
En pocas palabras, un algoritmo es una serie de pasos contenidos, que sigue para lograr algún objetivo o producir algún resultado. Tomemos, por ejemplo, la receta de tu abuela para hornear un pastel. Espera, ¿eso cuenta como un algoritmo? ¡Claro que sí!
function BakeCake(flavor, icing){ " 1. Heat Oven to 350 F 2. Mix flour, baking powder, salt 3. Beat butter and sugar until fluffy 4. Add eggs. 5. Mix in flour, baking powder, salt 6. Add milk and " + flavor + " 7. Mix further 8. Put in pan 9. Bake for 30 minutes 10." + if(icing === true) return 'add icing' + " 10. Stuff your face " } BakeCake('vanilla', true) => deliciousnessLos algoritmos son útiles en nuestro examen de la complejidad del tiempo porque vienen en todas las formas y tamaños.
De la misma manera que puede cortar un pastel de 100 formas diferentes, puede resolver un solo problema con muchos algoritmos diferentes. Algunas soluciones son más eficientes, toman menos tiempo y requieren menos espacio que otras.
Entonces, la pregunta principal es: ¿cómo hacemos para analizar qué soluciones son más eficientes?
¡Matemáticas al rescate! El análisis de la complejidad del tiempo en la programación es solo una forma matemática extremadamente simplificada de analizar cuánto tiempo tomará un algoritmo con un número determinado de entradas (n) para completar su tarea. Por lo general, se define mediante la notación Big-O .
¿Qué es la notación Big O?
Si prometes que no te rendirás y dejarás de leer, te lo diré.
La notación Big-O es una forma de convertir los pasos generales de un algoritmo en términos algebraicos, y luego excluir constantes y coeficientes de orden inferior que no tienen un impacto tan grande en la complejidad general del problema.
Los matemáticos probablemente se avergüencen un poco de mi suposición de "impacto general" allí, pero para que los desarrolladores ahorren tiempo, es más fácil simplificar las cosas de esta manera:
Regular Big-O 2 O(1) --> It's just a constant number 2n + 10 O(n) --> n has the largest effect 5n^2 O(n^2) --> n^2 has the largest effectEn resumen, todo lo que dice este ejemplo es: solo miramos el factor en nuestra expresión que tiene el mayor impacto potencial en el valor que devolverá nuestra expresión. (Esto cambia a medida que la constante se vuelve extremadamente grande yn se vuelve pequeña, pero no nos preocupemos por eso por ahora).
A continuación se muestran algunas complejidades de tiempo comunes con definiciones simples. No dude en consultar Wikipedia, sin embargo, para obtener definiciones más detalladas.
- O (1) - Tiempo constante: Dada una entrada de tamaño n, solo se necesita un paso para que el algoritmo realice la tarea.
- O (log n) - Tiempo logarítmico: dada una entrada de tamaño n, el número de pasos necesarios para realizar la tarea se reduce en algún factor con cada paso.
- O (n) - Tiempo lineal: Dada una entrada de tamaño n, el número de pasos requeridos está directamente relacionado (1 a 1)
- O (n²) - Tiempo cuadrático: Dada una entrada de tamaño n, el número de pasos necesarios para realizar una tarea es cuadrado de n.
- O (C ^ n) - Tiempo exponencial: dada una entrada de tamaño n, el número de pasos necesarios para realizar una tarea es una constante de la potencia n (número bastante grande).
Con este conocimiento en la mano, veamos la cantidad de pasos que conlleva cada una de estas complejidades temporales:
let n = 16; O (1) = 1 step "(awesome!)" O (log n) = 4 steps "(awesome!)" -- assumed base 2 O (n) = 16 steps "(pretty good!)" O(n^2) = 256 steps "(uhh..we can work with this?)" O(2^n) = 65,536 steps "(...)"Como puede ver, las cosas pueden convertirse fácilmente en órdenes de magnitud más complejas dependiendo de la complejidad de su algoritmo. Afortunadamente, las computadoras son lo suficientemente potentes como para manejar complejidades realmente grandes con relativa rapidez.
Entonces, ¿cómo analizamos nuestro código con la notación Big-O?
Bueno, aquí hay algunos ejemplos rápidos y simples de cómo puede aplicar este conocimiento a algoritmos que puede encontrar en la naturaleza o codificar usted mismo.
Usaremos las estructuras de datos a continuación para nuestros ejemplos:
var friends = { 'Mark' : true, 'Amy' : true, 'Carl' : false, 'Ray' : true, 'Laura' : false, } var sortedAges = [22, 24, 27, 29, 31]O (1) - Tiempo constante
Las búsquedas de valores cuando se sabe que la clave (objetos) o el índice (matrices) siempre dan un paso y, por lo tanto, son un tiempo constante.
//If I know the persons name, I only have to take one step to check: function isFriend(name){ //similar to knowing the index in an Array return friends[name]; }; isFriend('Mark') // returns True and only took one step function add(num1,num2){ // I have two numbers, takes one step to return the value return num1 + num2 }O (log n) - Tiempo logarítmico
Si sabe en qué lado de la matriz buscar un elemento, ahorrará tiempo al cortar la otra mitad.
//You decrease the amount of work you have to do with each step function thisOld(num, array){ var midPoint = Math.floor( array.length /2 ); if( array[midPoint] === num) return true; if( array[midPoint] only look at second half of the array if( array[midpoint] > num ) --> only look at first half of the array //recursively repeat until you arrive at your solution } thisOld(29, sortedAges) // returns true //Notes //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation. //This solution works because our Array is sorted //Recursive solutions are often logarithmic //We'll get into recursion in another post!O (n) - Tiempo lineal
Tiene que mirar cada elemento de la matriz o lista para realizar la tarea. Los bucles for simples son casi siempre de tiempo lineal. Además, los métodos de matriz como indexOf también son tiempo lineal. Simplemente estás abstraído del proceso de bucle.
//The number of steps you take is directly correlated to the your input size function addAges(array){ var sum = 0; for (let i=0 ; i < array.length; i++){ //has to go through each value sum += array[i] } return sum; } addAges(sortedAges) //133O (n²): tiempo cuadrático
Los bucles for anidados son de tiempo cuadrático, porque está ejecutando una operación lineal dentro de otra operación lineal (o n * n = n²).
//The number of steps you take is your input size squared function addedAges(array){ var addedAge = []; for (let i=0 ; i < array.length; i++){ //has to go through each value for(let j=i+1 ; j < array.length ; j++){ //and go through them again addedAge.push(array[i] + array[j]); } } return addedAge; } addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ] //Notes //Nested for loops. If one for loop is linear time (n) //Then two nested for loops are (n * n) or (n^2) Quadratic!O (2 ^ n) - Tiempo exponencial
El tiempo exponencial suele ser para situaciones en las que no sabes mucho y tienes que probar todas las combinaciones o permutaciones posibles.
//The number of steps it takes to accomplish a task is a constant to the n power //Thought example //Trying to find every combination of letters for a password of length nDebe realizar un análisis de la complejidad del tiempo cada vez que escriba un código que deba ejecutarse rápidamente.
Cuando tiene varias rutas para resolver un problema, definitivamente es más prudente crear una solución que simplemente funcione primero. Pero a la larga, querrá una solución que se ejecute de la manera más rápida y eficiente posible.
Para ayudarlo con el proceso de resolución de problemas, aquí hay algunas preguntas simples para hacer:
1. ¿Resuelve esto el problema? Si =>2. ¿Tiene tiempo para trabajar en esto?
Sí => vaya al paso 3
No => Vuelva a él más tarde y vaya al paso 6 por ahora.
3. ¿Cubre todos los casos extremos? Si =>
4. ¿Son mis complejidades lo más bajas posible?
No => reescribir o modificar en una nueva solución -> volver al paso 1
Sí => vaya al paso 5
5. ¿Está mi código SECO? Si =>
6. ¡Regocíjate!
No => Make it D.R.Y, then rejoice!
Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.
Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.
You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.
Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.
Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.
The ability to describe a better solution usually springs from some semblance of time complexity analysis.
In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.
Here’s a final recap:
- O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
- O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
- O(n) — Linear Time: The number of of steps required are directly related (1 to 1).
- O(n²) — Quadratic Time: The number of steps it takes to accomplish a task is square of n.
- O(C^n) — Exponential: The number of steps it takes to accomplish a task is a constant to the n power (pretty large number).
And here are some helpful resources to learn more:
- Wikipedia
- The Big O Cheat Sheet is a great resource with common algorithmic time complexities and a graphical representation. Check it out!