¿Qué significa realmente la complejidad temporal O(log n)? by@maazrk
249,516 lecturas

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

2017/05/28
por @maazrk 249,516 lecturas
ES
Read on Terminal Reader

Demasiado Largo; Para Leer


Company Mentioned

Mention Thumbnail
featured image - ¿Qué significa realmente la complejidad temporal O(log n)?
react to story with heart

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.

image

Una matriz ordenada de 16 elementos.

image

Seleccionando el elemento central como pivote (longitud / 2)

image

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

image

Repetir el proceso para encontrar el elemento medio para cada subarreglo

image

image

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,

image

Fórmula simplificada

Del mismo modo, para n elementos,

image

Generalización

image

Separando la potencia para el numerador y el denominador

image

Multiplicando ambos lados por 2^k

image

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

image

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!

HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa