Hablemos de algoritmos, eficiencia y esas cosas, es decir, hablemos de cosas 'chungas'.
Para medir la eficiencia de los algoritmos no usamos el tiempo propiamente dicho (como podríamos pensar en un primer momento), si lo midiéramos mediante algo temporal, como segundos, milisegundos o cosas así los datos no serían fiables, ya que dependen del hardware y de lo que esté haciendo en ese momento el ordenador.
En su lugar usamos 2 tipos de medidas:
- Time complexity (complejidad temporal).
- Space complexity (complejidad espacial) o también lo podríamos llamar Auxiliary Space complexity (luego hablaremos de esto).
Y para cualquiera de estos tipos de medida usamos lo que se conoce como Big O notation o notación de Landau. No vamos a entrar en la matemática específica de esto, si queréis saber más tenéis más información aquí. En nuestro caso valdrá con que tengamos este diagrama como referencia
Siendo O(1) lo mejor y O(n^2) lo peor. Con esto como base empecemos.
TIME COMPLEXITY
Al contrario de lo que indica su nombre no es una regla de medida temporal, lo que hace es medir la efeciencia basándose en el número de operaciones simples que realiza la función, entendiendo por operaciones simples: =, +, -, *, /, %, <, >.
Veamoslo mejor con algunos ejemplos simples:
function addUpTo(n) {
let total = 0;
for (let i= 0; i <= n; i++) {
total += i;
}
return total;
}
Veamos cuantas operaciones tenemos aquí:
- let total=0: Primera asignación que ocurre solo 1 vez.
- let i=0: Segunda asignación que ocurre solo 1 vez.
3 y 4. i <= n: Que se divide en 2 comparaciones 1 por el < y otra por el = y esto se haría n veces.
5 y 6. i++: Esto es una suma y una asignación a i que se produce a su vez n veces.
7 y 8. total += i: Y esto es igual que el anterior una suma y una asignación que se produce n veces.
En este caso tenemos 2 operaciones simples que se producen solo 1 vez y luego 6 operaciones que se producen n veces, es decir, que dependen de n, por lo tanto ¿cual creéis que será el TIME COMPLEXITY en este caso? Pensemos que son todo operaciones simples pero que dependen de n, por lo que en este caso nuestro valor será O(n).
Vayamos ahora con otro ejemplo:
function addUpToV2(n) {
return n * (n + 1) / 2;
}
Es la misma función, es decir, hace lo mismo, nos devuelve la suma de todos los valores menores que n incluido n. Veamos las operaciones:
- n+1: Operación suma que se produce 1 vez.
- n * (resultado de lo anterior): Multiplicación del resultado anterior que se produce 1 vez.
- resultado anterior/2: División del resultado anterior que se produce solo 1 vez.
En este caso tenemos solo 3 operaciones pero además estas operaciones solo se producen una vez, es decir, no dependen de n, por lo tanto, en este caso el valor sería O(1) puesto que pasemos el número que pasemos a n siempre es constante la cantidad de operaciones que se realizarán.
Otro ejemplo:
function countUpAndDown(n){
console.log("Hacia arriba...");
for (let i = 0; i < n; i++) {
console.log(i);
}
console.log("En la cima \n Bajando...");
for (let j = n -1; j >= 0; j--) {
console.log(j);
}
console.log("Bajamos!!");
}
En este caso tenemos 2 bucles que como ya hemos visto cada una sería O(n), es decir, O(2n). Es 2n porque depende 2 veces de n, pero al medir la complejidad siempre ignoramos los valores numéricos constantes por lo que volvemos a tener una función con un valor de 0(n).
Y ahora vamos con el último ejemplo con las medidas simples de medida (de momento no entramos a las medidas logarítmicas).
function printAllPairs (n){
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i,j);
}
}
}
Aquí tenemos otro par de bucles, pero en este caso son 2 bucles anidados, es decir, uno dentro de otro, por lo que sería un n veces del bucle interior, por cada n veces del bucle superior, es decir, n*n o n^2, resumiendo en este caso tendríamos la peor medida de todas O(n^2).
Hasta aquí de momento en cuanto al Time Complexity, más adelante volveremos a ello, ahora vamos a por el Space Complexity
SPACE COMPLEXITY
Cuando hablamos de la complejidad espacial, nos referimos a cuanta memoria necesitaremos para ejecutar nuestra función. Al igual que con la time complexity, se usa para medir O, lo único que en este caso lo que diferenciamos será:
- Valores primitivos: number, boolean, undefined y null. Estos valores son siempre constantes en cuanto a su tamaño por lo que ocuparán O(1).
- Objetos y arrays: Que en este caso se miden en O(n) siendo n la cantidad de keys en los objetos y siendo n el tamaño de array.
En este caso la diferenciación es simple, si no tiene arrays u objetos será O(1), si tiene n arrays u objetos O(n) y si tiene arrays u objetos anidados entre sí sería O(n^x) siendo x la cantidad de anidación que tengamos, es decir, si tenemos un array de 3 dimensiones tendremos un O(n^3), si tenemos uno de 2 O(n^2).
Esto en cuanto a la parte simple del space complexity y del time complexity, evidentemente todo esto tiene algo más de chicha cuando entramos en los resultados intermedios de la gráfica (si, esos que contienen logaritmos). Hagamos un repaso de los logaritmos
LOGARITMOS
Hablemos ahora de los logaritmos, puesto que aunque no los hayamos visto todavía en algún ejemplo si que forman parte de las mediciones de eficiencia de los algoritmos. Si os fijáis en la gráfica inicial están presentes en las mediciones intermedias.
Pues veamos, ¿qué es un logaritmo? Para ponerlo simple es lo contrario que un exponente, es decir, ¿cuál es el resultado de 2^4? (2 elevado a 4)?
16
Por lo que entonces sería:
Una definición más específica sería:
Un logaritmo es la cantidad de veces que tengo que dividir un número por 2 (si es de base 2) hasta tener un valor menor o igual a 1. En nuestro caso serían 4 las veces que tenemos que dividir 16:
- 16 / 2 = 8
- 8 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
Y a la hora de hablar de logaritmos, por defecto siempre hablamos de logaritmos base 2, por lo que lo podemos omitir (y así es como lo vemos en las gráficas).
Bueno y hasta aquí lo básico, nos vemos en el siguiente, un abrazooorrrrr.