¿Qué significa realmente la complejidad temporal O(log n)?

Conocer de antemano la complejidad de los algoritmos es una cosa, y otra cosa es saber por qué es así.

Si usted es un graduado de informática o alguien que quiere lidiar con problemas de optimización de manera efectiva, esto es algo que debe comprender si desea utilizar su conocimiento para resolver problemas reales.

Complejidades como O(1) y O(n) son simples y directas. O(1) significa una operación que se realiza para llegar a un elemento directamente (como un diccionario o una tabla hash), O(n) significa que primero tendríamos que buscarlo comprobando n elementos, pero ¿qué podría hacer O(log n)? ¿significar?

Un lugar donde es posible que haya oído hablar de la complejidad del tiempo O (log n) la primera vez es el algoritmo de búsqueda binaria. Por lo tanto, debe haber algún tipo de comportamiento que el algoritmo muestre para que se le dé una complejidad de log n. Veamos cómo funciona.

Dado que la búsqueda binaria tiene una eficiencia en el mejor de los casos de O(1) y una eficiencia en el peor de los casos (caso promedio) de O(log n), veremos un ejemplo del peor de los casos. Considere una matriz ordenada de 16 elementos.

Para el peor de los casos, digamos que queremos buscar el número 13.

Una matriz ordenada de 16 elementos.

Seleccionando el elemento central como pivote (longitud / 2)

Dado que 13 es menor que el pivote, eliminamos la otra mitad de la matriz

Repetir el proceso para encontrar el elemento medio para cada subarreglo

Puede ver que después de cada comparación con el término medio, nuestro rango de búsqueda se divide en la mitad del rango actual.

Entonces, para llegar a un elemento de un conjunto de 16 elementos, tuvimos que dividir la matriz 4 veces,

Podemos decir eso,

Fórmula simplificada

Del mismo modo, para n elementos,

Generalización

Separando la potencia para el numerador y el denominador

Multiplicando ambos lados por 2^k

Resultado final

Ahora, veamos la definición de logaritmo, dice que

Una cantidad que representa la potencia a la que debe elevarse un número fijo (la base) para producir un número dado.

Lo que convierte nuestra ecuación en

Forma logarítmica

Entonces, el log n en realidad significa algo, ¿no es así? Un tipo de comportamiento que nada más puede representar.

Bueno, espero que la idea esté clara en tu mente. Cuando se trabaja en el campo de la informática, siempre es útil saber esas cosas (y también es bastante interesante). Quién sabe, tal vez usted sea el miembro de su equipo capaz de encontrar una solución optimizada para un problema, solo porque sabe a lo que se enfrenta. ¡Buena suerte!