¿Qué significa O(log n)exactamente

time-complexity big-o


Estoy aprendiendo sobre los tiempos de ejecución de Big O Notation y los tiempos amortizados. Entiendo la noción de tiempo lineal O (n) , lo que significa que el tamaño de la entrada afecta el 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 factoriales.

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 gran detalle) qué es el logaritmo, en el sentido de que: log 10 100 = 2, pero no puedo entender cómo identificar una función con un tiempo logarítmico.




Answer 1 John Feminella


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.

or

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

Esta es la razón por la cual, por ejemplo, buscar personas en una guía telefónica es O (log n). No necesita verificar a cada persona en la guía telefónica para encontrar la correcta; en su lugar, simplemente puede dividir y conquistar mirando en función de dónde está su nombre alfabéticamente, y en cada sección solo necesita explorar un subconjunto de cada sección antes de encontrar 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 ejecución. Asumiremos que nuestra guía telefónica tiene negocios (las "Páginas amarillas") que tienen nombres únicos y personas (las "Páginas blancas") que pueden no tener nombres únicos. Se asigna un número de teléfono como máximo a una persona o empresa. También asumiremos que lleva tiempo constante pasar a una página específica.

Aquí están los tiempos de ejecución de algunas operaciones que podríamos realizar en la guía telefónica,de las más rápidas a las más lentas:

  • O (1) (en el peor de los casos): dada la página en la que se encuentra el nombre de una empresa y el nombre de la empresa, busque el número de teléfono.

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

  • O (log n): dado el nombre de una persona, encuentre el número de teléfono seleccionando un punto aleatorio a la mitad de la parte del libro que aún no ha buscado, y luego verifique si el nombre de la persona está en ese punto. Luego repita 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): busca todas las personas cuyos números de teléfono contienen el dígito "5".

  • O (n): dado un número de teléfono, encuentre a la persona o empresa con ese número.

  • O (n log n): Hubo una confusión en la oficina de la impresora, 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 en cada página y luego colocando 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, luego encerrar en un círculo su nombre en el libro 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" adicional al final del número de teléfono. Toma un poco de blanqueamiento y elimina cada cero.

  • O (n · n!): Estamos listos para cargar las guías telefónicas en el muelle de envío. Desafortunadamente, el robot que se suponía que debía cargar los libros se volvió loco: ¡está poniendo los libros en el camión en un orden aleatorio! Peor aún, carga todos los libros en el camión, luego verifica si están en el orden correcto, y si no, los descarga y comienza 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 hace una broma y conecta 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 fábrica realiza una ejecución duplicada 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 aún más copias cuando encuentra un libro duplicado para cargar, pero todavía tiene que cargar cada libro original y duplicado que se haya impreso.




Answer 2 fastcodejava


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

Es O(log n) cuando dividimos y conquistamos tipos de algoritmos, por ejemplo, búsqueda binaria. Otro ejemplo es la ordenación rápida en la que cada vez que dividimos la matriz en dos partes y cada vez que le lleva tiempo O(N) encontrar un elemento pivote. Por lo tanto N O(log N)




Answer 3 Jørn Schou-Rode


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. Observe cómo cada nivel contiene el doble del número de nodos en comparación con el nivel anterior (por lo tanto, binario ):

Binary tree

La búsqueda binaria es un ejemplo con complejidad O(log n) . Digamos que los nodos en el nivel inferior del árbol en la figura 1 representan elementos en alguna colección ordenada. La búsqueda binaria es un algoritmo de divide y vencerás, y el dibujo muestra cómo necesitaremos (como máximo) 4 comparaciones para encontrar el registro que estamos buscando 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 estamos buscando,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.

Al trazar log(n) en una hoja de papel normal, se obtendrá un gráfico donde el aumento de la curva se desacelera a medida que n aumenta:

O(log n)




Answer 4 2cupsOfTech


La explicación a continuación utiliza el caso de un árbol binario completamente equilibrado para ayudarlo a comprender cómo obtenemos la complejidad del tiempo logarítmico.

El árbol binario es un caso en el que un problema de tamaño n se divide en un sub-problema de tamaño n/2 hasta llegar a un problema de tamaño 1:

height of a binary tree

Y así es como se obtiene O(log n)que es la cantidad de trabajo que hay que hacer en el árbol anterior para llegar a una solución.

Un algoritmo común con una complejidad temporal de O(log n)es la Búsqueda Binaria cuya relación recursiva es T(n/2)+O(1),es decir,en cada nivel posterior del árbol se divide el problema en la mitad y se hace una cantidad constante de trabajo adicional.




Answer 5 James Oravec


Overview

Otros han dado buenos ejemplos de diagramas,como los diagramas de árboles.No he visto ningún ejemplo de código simple.Así que además de mi explicación,proporcionaré algunos algoritmos con simples declaraciones de impresión para ilustrar la complejidad de las diferentes categorías de algoritmos.

Primero, querrás tener una idea general del Logaritmo, que puedes obtener en https://en.wikipedia.org/wiki/Logarithm . El uso de la ciencia natural e y el registro natural. Los discípulos de ingeniería usarán log_10 (log base 10) y los informáticos usarán log_2 (log base 2) mucho, ya que las computadoras están basadas en binarios. A veces verá abreviaturas de log natural como ln() , los ingenieros normalmente dejan el _10 apagado y solo usan log() y log_2 se abrevia como lg() . Todos los tipos de logaritmos crecen de manera similar, es por eso que comparten la misma categoría de log(n) .

Cuando se miran los ejemplos de código que se muestran a continuación,recomiendo mirar O(1),luego O(n),y luego O(n^2).Después de que seas bueno con esos,entonces mira los otros.He incluido ejemplos limpios así como variaciones para demostrar cómo los cambios sutiles pueden aún resultar en la misma categorización.

Puedes pensar en O(1),O(n),O(logn),etc.como clases o categorías de crecimiento.Algunas categorías tomarán más tiempo que otras.Estas categorías ayudan a darnos una forma de ordenar el rendimiento del algoritmo.Algunas crecieron más rápido a medida que la entrada n crece.La siguiente tabla demuestra dicho crecimiento numéricamente.En la tabla siguiente piensa en log(n)como el techo de log_2.

enter image description here

Ejemplos de código simple de varias categorías Big O:

O (1) - Ejemplos de tiempo constante:

  • Algoritmo 1:

El algoritmo 1 imprime hola una vez y no depende de n, por lo que siempre se ejecutará en tiempo constante, por lo que es O(1) .

print "hello";
  • Algoritmo 2:

El algoritmo 2 imprime hola 3 veces, sin embargo, no depende de un tamaño de entrada. Incluso cuando n crece, este algoritmo siempre imprimirá hola 3 veces. Dicho esto 3, es una constante, por lo que este algoritmo también es O(1) .

print "hello";
print "hello";
print "hello";

O (log (n)) - Ejemplos logarítmicos:

  • Algoritmo 3: esto actúa como "log_2"

El algoritmo 3 demuestra un algoritmo que se ejecuta en log_2 (n). Note la operación de post de la para múltiplos de bucle el valor actual de i por 2, por lo que i va de 1 a 2 a 4 a 8 para 16 a 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algoritmo 4: esto actúa como "log_3"

El algoritmo 4 demuestra log_3. Noto i va de 1 a 3 para 9 al 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algoritmo 5: esto actúa como "log_1.02"

El algoritmo 5 es importante,ya que ayuda a mostrar que mientras el número sea mayor que 1 y el resultado se multiplique repetidamente contra sí mismo,se está viendo un algoritmo logarítmico.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Ejemplos de tiempo lineal:

  • Algoritmo 6

Este algoritmo es simple,que imprime hola n veces.

for(int i = 0; i < n; i++)
  print "hello";
  • Algoritmo 7

Este algoritmo muestra una variación,donde imprimirá hola n/2 veces.n/2=1/2*n.Ignoramos la constante 1/2 y vemos que este algoritmo es O(n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Ejemplos:

  • Algoritmo 8

Piense en esto como una combinación de O(log(n)) y O(n) . La anidación de los bucles for nos ayuda a obtener el O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algoritmo 9

El algoritmo 9 es como el algoritmo 8, pero cada uno de los bucles ha permitido variaciones, que aún dan como resultado que el resultado final sea O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n al cuadrado Ejemplos:

  • Algoritmo 10

O(n^2) se obtiene fácilmente anidando el estándar para bucles.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algoritmo 11

Como el algoritmo 10,pero con algunas variaciones.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubos Ejemplos:

  • Algoritmo 12

Esto es como el algoritmo 10,pero con 3 bucles en lugar de 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algoritmo 13

Como el algoritmo 12, pero con algunas variaciones que aún producen O(n^3) .

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Summary

Lo anterior da varios ejemplos directos y variaciones para ayudar a demostrar qué cambios sutiles pueden introducirse que realmente no cambian el análisis.Esperemos que te dé suficiente perspicacia.