1882 votos

¿Qué significa O(log n) exactamente?

Actualmente estoy aprendiendo sobre los tiempos de ejecución y los tiempos amortizados de la notación Big O. Entiendo la noción de O(n) tiempo lineal, lo que significa que el tamaño de la entrada afecta al crecimiento del algoritmo proporcionalmente... y lo mismo ocurre, por ejemplo, con el tiempo cuadrático O(n) 2 ) etc., incluso algoritmos, como los generadores de permutación, con ¡O(n)! veces, que crecen por los factores.

Por ejemplo, la siguiente función es O(n) porque el algoritmo crece en proporción a su entrada n :

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Del mismo modo, si hubiera un bucle anidado, el tiempo sería O(n) 2 ).

Pero, ¿qué es exactamente O(log n) ? Por ejemplo, ¿qué significa decir que la altura de un árbol binario completo es O(log n) ?

Sé (tal vez no con mucho detalle) lo que es el logaritmo, en el sentido de que: el log 10 100 = 2, pero no puedo entender cómo identificar una función con un tiempo logarítmico.

2406voto

John Feminella Puntos 116878

No puedo entender cómo identificar una función con un tiempo de registro.

Los atributos más comunes de la función de tiempo de ejecución logarítmica son que:

  • la elección del siguiente elemento sobre el cual realizar alguna acción es una de varias posibilidades, y
  • sólo uno tendrá que ser elegido.

o

  • los elementos sobre los que se realiza la acción son dígitos de n

Por eso, por ejemplo, buscar gente en una guía telefónica es O(log n). No necesitas comprobar cada persona en la guía telefónica para encontrar la correcta; en cambio, puedes simplemente dividir y conquistar, y sólo necesitas explorar una pequeña fracción de todo el espacio antes de que finalmente encuentres el número de teléfono de alguien.

Por supuesto, una guía telefónica más grande todavía le llevará más tiempo, pero no crecerá tan rápido como el aumento proporcional del tamaño adicional.


Podemos ampliar el ejemplo de la guía telefónica para comparar otros tipos de operaciones y su tiempo de funcionamiento. Asumiremos que nuestra guía telefónica tiene negocios (las "Páginas Amarillas") que tienen nombres únicos y gente (las "Páginas Blancas") que pueden no tener nombres únicos. Se asigna un número de teléfono a una persona o empresa como máximo. También asumiremos que toma tiempo constante para pasar a una página específica.

Aquí están los tiempos de algunas operaciones que podríamos realizar en la guía telefónica, de mejor a peor:

  • O(1) (el peor de los casos): Dada la página en la que está el nombre de la empresa y el nombre de la empresa, busca el número de teléfono.

  • O(1) (caso promedio): Dada la página en la que está el nombre de una persona y su nombre, busca el número de teléfono.

  • O(log n): Dado el nombre de una persona, encuentre el número de teléfono escogiendo un punto al azar aproximadamente a la mitad de la parte del libro que aún no ha buscado, y luego compruebe si el nombre de la persona está en ese punto. Luego repite el proceso a la mitad de la parte del libro donde se encuentra el nombre de la persona. (Esta es una búsqueda binaria del nombre de una persona).

  • O(n): Encuentra a todas las personas cuyos números de teléfono contengan el dígito "5".

  • O(n): Si le dan un número de teléfono, encuentre a la persona o negocio con ese número.

  • O(n log n): Hubo una confusión en la oficina de la imprenta, y nuestra guía telefónica tenía todas sus páginas insertadas en un orden aleatorio. Arregle el orden para que sea correcto mirando el primer nombre de cada página y luego ponga esa página en el lugar apropiado en una nueva guía telefónica vacía.

Para los siguientes ejemplos, estamos ahora en la oficina de la imprenta. Las guías telefónicas están esperando ser enviadas a cada residente o negocio, y hay una pegatina en cada guía telefónica identificando a dónde debe ser enviada. Cada persona o negocio recibe una guía telefónica.

  • O(n log n): Queremos personalizar la guía telefónica, así que vamos a encontrar el nombre de cada persona o empresa en su copia designada, y luego hacer un círculo con su nombre en la guía y escribir una breve nota de agradecimiento por su patrocinio.

  • O(n) 2 ): Se produjo un error en la oficina, y cada entrada en cada una de las guías telefónicas tiene un "0" extra al final del número de teléfono. Toma un poco de blanqueador y quita cada cero.

  • O(n - n!): Estamos listos para cargar las guías telefónicas en el muelle de embarque. Desafortunadamente, el robot que se suponía que iba a cargar las guías se ha vuelto loco: ¡está poniendo las guías en el camión en un orden aleatorio! Peor aún, carga todos los libros en el camión, luego comprueba si están en el orden correcto, y si no, los descarga y empieza de nuevo. (Este es el temido tipo bogo .)

  • O(n) n ): Arreglas el robot para que cargue las cosas correctamente. Al día siguiente, uno de tus compañeros de trabajo te gasta una broma y cablea el robot del muelle de carga a los sistemas de impresión automatizados. Cada vez que el robot va a cargar un libro original, la impresora de la fábrica hace un duplicado de todas las guías telefónicas. Afortunadamente, los sistemas de detección de errores del robot son lo suficientemente sofisticados como para que el robot no intente imprimir más copias cuando se encuentra con un libro duplicado para cargarlo, pero aún así tiene que cargar cada libro original y duplicado que se ha impreso.

539voto

Jørn Schou-Rode Puntos 19947

Ya se han publicado muchas buenas respuestas a esta pregunta, pero creo que nos falta una importante, a saber, la respuesta ilustrada.

¿Qué significa decir que la altura de un árbol binario completo es O(log n)?

El siguiente dibujo representa un árbol binario. Obsérvese cómo cada nivel contiene el doble de nodos en comparación con el nivel anterior (por lo tanto binario ):

Binary tree

La búsqueda binaria es un ejemplo de complejidad O(log n) . Digamos que los nodos en el nivel inferior del árbol de la figura 1 representan artículos de alguna colección ordenada. La búsqueda binaria es un algoritmo de dividir y conquistar, y el dibujo muestra cómo necesitaremos (como mucho) 4 comparaciones para encontrar el registro que buscamos en este conjunto de datos de 16 elementos.

Supongamos que en su lugar tuviéramos un conjunto de datos con 32 elementos. Continúa el dibujo anterior para encontrar que ahora necesitaremos 5 comparaciones para encontrar lo que buscamos, ya que el árbol sólo ha crecido un nivel más cuando multiplicamos la cantidad de datos. Como resultado, la complejidad del algoritmo puede describirse como un orden logarítmico.

Trazado log(n) en una hoja de papel normal, resultará en un gráfico donde la subida de la curva se desacelera a medida que n aumenta:

O(log n)

511voto

fastcodejava Puntos 22174

O(log n) básicamente significa que el tiempo sube linealmente mientras que el n sube exponencialmente. Así que si se necesita 1 segundo para calcular 10 elementos, tomará 2 segundos para calcular 100 elementos, 3 segundos para calcular 1000 elementos, y así sucesivamente.

220voto

2cupsOfTech Puntos 1541

El árbol binario es un caso especial en el que un problema de tamaño n se divide en un sub-problema de tamaño n/2. Permítanme mostrarles cómo se calcula la altura del árbol en el que un problema se divide en subproblemas de tamaño b hasta que recursivamente llegamos a un problema de tamaño 1. Recursive tree height with sub-problem of size b

90voto

Anon. Puntos 26829

Tiempo de funcionamiento logarítmico ( O(log n) ) significa esencialmente que el tiempo de funcionamiento crece en proporción a la logaritmo del tamaño de la entrada - como ejemplo, si 10 elementos toman como máximo alguna cantidad de tiempo x y 100 artículos toma como máximo, digamos, 2x y 10.000 artículos toma a lo sumo 4x entonces se ve como un O(log n) la complejidad del tiempo.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X