Entender la base de Logaritmo

Antes de explicar el Big O notation es necesario explicar qué es un logaritmo. Un logaritmo es preguntar cuántas multiplicaciones del mismo número X son necesarias para llegar a un número Y.

EJ: \(2^x= 8\)¿Cuántos 2 tengo que multiplicar para llegar a 8? \(2^3 = 8\)

Lo que quiere decir que \(Log_{2}(8)=3\). El número debajo del Log 2 es el número a multiplicar, el número entre paréntesis 8 es el número al que se quiere llegar, el resultado 3 es el número de veces que hay que multiplicar el \(Log_{x}\) en este caso 2.

Otro ejemplo sería el logaritmo de 1024 en el que hay que calcular el número del exponente necesario para llegar a ese número, es decir \(2^x = 1024\).

$$2^{10} = 1024 == Log_{2}(1024) = 10$$

Existen otros logaritmos como \(Log_{10}\), que sería calcular \(10^x\), pero con entender \(Log_{2}\) es suficiente.

Introducción

Big O notation, es la representación de como escala un algoritmo según va subiendo la cantidad de parámetros, representa qué tan rápido es el algoritmo.

Es decir puedes tener dos algoritmos y que uno crezca exponencialmente más que otro. Por ejemplo.

Se ve claramente como la búsqueda lineal aumenta mas su tiempo cuando le añades más elementos que en la búsqueda binaria.

Big \(O(n)\) y \(O(log(n))\)

La búsqueda lineal significa que va tener que ir elemento por elemento hasta encontrar el elemento que estaba buscando. Empieza por el primer elemento, ¿es el que busco? no, pasó al segundo elemento y así hasta encontrar el elemento.

Por lo que para una lista de \(n\) elementos, el número de búsquedas que va tener que hacer es de \(n\) veces, en el peor de los casos, es decir que sea el último elemento. Esto quiere decir que para la búsqueda lineal el Big O notation es \(O(n)\). Se puede medir el Big O notation del “mejor caso”, el “caso promedio” y el “peor caso”. Pero el más común y al que nos vamos referir siempre en este post es el de “peor caso”.

Para ver un ejemplo de \(O(log(n)\) entenderemos la búsqueda binaria que parte de una lista ordenada:

[1, 2, 3, 4, 5, 6, 7].

Supongamos que buscamos el número 5 con la búsqueda binaria, así es como funciona:

En el caso de la búsqueda binaria el número de elementos de la lista, no es el mismo que el número búsquedas que tenemos que hacer. El anterior ejemplo de búsqueda binaria es el peor caso, que se podía dar y solo ha hecho falta 3 iteraciones, para obtener el peor caso (5), el peor caso puede ser cualquiera de estos (1,3,5,7) en una lista de 7. En cambio en una búsqueda lineal el peor caso de una lista de 7 serian 7 iteraciones.

Dado que el número de iteraciones depende del algoritmo el tipo de Big O notation del algoritmo, es de \(O(log(n))\), lo que quiere decir que es un algoritmo más rápido que el búsqueda lineal.

Big \(O(n!)\), \(O(n²)\) y \(O(1)\)

Aquí una gráfica donde se ven todos los Big O notation y como aumentan las operaciones que hacen cuando aumenta el número de entrada del algoritmo como puede ser el tamaño de una lista.

En los ejemplos anteriores hemos visto algoritmos de \(O(n)\) búsqueda lineal y de \(O(log(n))\) búsqueda binaria.

Ahora vamos a ver los que faltan \(O(n!)\), \(O(n²)\) y \(O(1)\)

\(O(1)\)

\(O(1)\) es el más sencillo, este es un algoritmo que solo necesita una iteración para completarse, puede ser por ejemplo la búsqueda de un objeto por la clave dentro de Map.

        Map<String, String> dniMap = Map.of(
                "12345678A", "María Lopez Marrero",
                "87654321B", "Juan Pérez Armas"
        );
        String nameClient = dniMap.get("12345678A"); //Esto lo hace en O(1), aunque el tamaño del map sea de 100 
        System.out.println(nameClient); // "María Lopez Marrero"

\(O(n²)\)

Esta O significa que crece cuadráticamente. Un ejemplo muy sencillo sería un típico doble bucle anidado, es decir un for dentro de un for, el bucle exterior se ejecuta \(n\) veces, y para cada iteración del bucle exterior, el bucle interior también se ejecuta \(n\) veces. Esto resulta en un total de \(n *n = n^2\)operaciones en el peor de los casos.

Hay varios algoritmos de ordenación que tienen esta anotación uno de los más famosos es Bubble Sort. Este algoritmo consiste en comparar el primer objeto con el segundo y si el primero es más grande los intercambia, compara el segundo con el tercero y así hasta el final, el elemento más grande se encuentra garantizado en la última posición. Por lo tanto, en la siguiente pasada, solo necesitamos ordenar hasta el penúltimo elemento por lo que con cada iteración tienes que recorrer \(n-1\) , en el peor de los casos.

\(O(n!)\)

La anotación n exponencial es la anotación más lenta de las Big O notation, por lo que siempre deberíamos evitar que nuestros algoritmos llegen hasta este punto, lo curioso es que hay problemas que no hay forma más eficiente hasta ahora de resolverlos que no sea con un algoritmo cuya anotación sea de \(O(n!)\).

El ejemplo que te voy exponer se llama el problema del viajero o the traveling salesperson problem. En mi ejemplo será un repartidor de correos por ser un poco más actual. Supongamos que tenemos que repartir 5 paquetes a sus respectivos 5 destinos. ¿Cómo podemos saber cual es la ruta más corta para repartir los paquetes? Si hay 5 sitios las combinaciones de rutas son de 120

$$(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120)$$

Cómo se ve en la fórmula exponencial cada vez que añadamos un sitio mas, el numero de posibilidades aumenta enormemente.

Por lo que la única forma de calcular cual es la ruta más corta, es calculando por cada ruta su km totales y una vez obtenidos todos quedarte con el menor. Como puedes ver en este caso es muy complicado o sino imposible pretender bajar del \(O(n!)\). Aquí tienes un enlace con información si quieres saber más del problema del viajero.

Conclusión

En este post, has visto que es un logaritmo, que es una big o notation, y una explicación con un ejemplo práctico de cada Big O. Espero que te haya servido para hacer tus programas más rápidos 🚀