10/08/2020
Estamos muy contentos por la convocatoria que tuvo nuestra búsqueda de desarrolladores Jr / Trainee , corregimos más de 800 exámenes.
Y ya están los seleccionados para la próxima etapa. Pronto todos serán notificados.
Queremos aprovechar esta publicación para ayudar a los desarrolladores en búsqueda de su primer experiencia.
Notamos que muchos de los postulantes tenían errores en común por lo que vamos a realizar una serie de posteos, no sólo para ayudar a nuestros candidatos sino también para todos los que están en su primer búsqueda laboral.
En esta oportunidad vamos a hablar de la complejidad temporal.
Qué es la complejidad temporal?
Por qué es importante saber que es la complejidad temporal?
Cómo se calcula la complejidad temporal?
Para analizar un algoritmo, generalmente se usa la complejidad temporal para obtener un estimado del tiempo de ejecución expresado en función del tamaño de la entrada. El resultado es típicamente expresado en notación “big O”. Esto suele ser útil para comparar algoritmos, especialmente cuando se necesita procesar una gran cantidad de datos.
La forma más sencilla para entender lo que realmente es la complejidad algorítmica es pensar en el ritmo de crecimiento, donde evaluaremos cómo crece el número de instrucciones necesarias para resolver el problema en función del tamaño del mismo. De esta manera nos olvidamos del lenguaje utilizado, el tiempo de ejecución, la cantidad de memoria consumida, el procesador utilizado, el sistema en donde se corra el algoritmo y el estilo de programación implementado.
Ejemplo
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
doSomething() // complejidad o(1)
}
}
}
El algoritmo aquí presentado tiene una complejidad O(n^3) ya que tiene una triple iteración anidada, por lo tanto el crecimiento del tiempo de ejecución de la fusión dependiendo del tamaño de la entrada (variable N), crecerá de manera cuadrática en orden 3.
Dado un N = 1 la cantidad de veces que se ejecutará la función doSOmething() será 1,
dado un N = 2 se ejecutará 8 veces, dado un N = 3 se ejecutará 27 y dado un N = 10 serán 1000 ejecuciones!!
Ya pueden comprender cómo crecerá el tiempo de ejecución de la función. Por eso es muy importante intentar diseñar algoritmos con baja complejidad temporal, como O(1), O(log n) o O(n).
Un simple experimento: Corran el siguiente código en un intérprete js y publiquen sus resultados para ver por qué la complejidad temporal no se calcula en base al tiempo, incluso pueden intentarlo más de una vez, nunca tardará lo mismo.
var t0 = performance.now()
var count = 0;
for (i = 0; i < 100; i++) {
for (j = 0; j < 100; j++) {
for (k = 0; k < 100; k++) {
count++
}
}
}
var t1 = performance.now();
console.log("La triple iteración anidada tomo " + (t1 - t0) + " milisegundos en ejecutar " + count + " instrucciones");
Esperemos que les haya servido para seguir potenciando su entendimiento sobre la complejidad temporal, y su importancia.
Cualquier consulta extra, pueden comunicarse con nosotros vía mail o por nuestra página web.
