Pregunta ¿Qué significa O (log n) exactamente?


Actualmente estoy aprendiendo sobre los tiempos de ejecución de la notación Big O y los tiempos amortizados. Entiendo la noción de En) tiempo lineal, 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 En2) etc.incluso algoritmos, como generadores de permutación, con ¡En!) veces, que crecen por factoriales.

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

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

Del mismo modo, si hubiera un ciclo anidado, el tiempo sería O (n2)

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


1732
2018-02-21 20:05


origen


Respuestas:


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

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

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

o

  • 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 cada persona en la guía telefónica para encontrar la correcta; en su lugar, puede simplemente dividir y conquistar al buscar según su nombre alfabéticamente, y en cada sección solo necesita explorar un subconjunto de cada sección antes de que finalmente encuentre el número de teléfono de otra persona.

Por supuesto, una guía telefónica más grande aún le llevará más tiempo, pero no crecerá tan rápido como el aumento proporcional en el 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 gente (las "Páginas blancas") que pueden no tener nombres únicos. Un número de teléfono se asigna como máximo a una persona o empresa. También asumiremos que lleva tiempo constante pasar a una página específica.

Estos son los tiempos de ejecución de algunas operaciones que podríamos realizar en la guía telefónica, de mejor a peor:

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

  • O (1) (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, busque el número de teléfono eligiendo un punto al azar a la mitad de la parte del libro que aún no ha buscado, 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 para el nombre de una persona).

  • En): Encuentra todas las personas cuyos números de teléfono contienen el dígito "5".

  • En): Dado un número de teléfono, encuentre 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. Repare el pedido para que sea correcto mirando el primer nombre en cada página y luego coloque esa página en el lugar apropiado en una nueva libreta telefónica vacía.

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

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

  • En2) 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. Tome un blanco y elimine cada cero.

  • O (n · n!): Estamos listos para cargar las guías telefónicas en el muelle de envío. Desafortunadamente, el robot que debía cargar los libros se ha vuelto 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 vuelve a empezar. (Este es el temido tipo bogo.)

  • Ennorte) Arreglas el robot para que esté cargando 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 automática. ¡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 aún tiene que cargar todos los libros originales y duplicados que se hayan impreso.


2177
2018-02-21 20:14



Ya se han publicado muchas buenas respuestas a esta pregunta, pero creo que realmente 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 muestra un árbol binario. Observe 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 con complejidad O(log n). Digamos que los nodos en el nivel inferior del árbol en la figura 1 representan elementos en una colección ordenada. La búsqueda binaria es un algoritmo de dividir y vencer, 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 tenemos un conjunto de datos con 32 elementos. Continúa el dibujo de arriba para encontrar que ahora necesitaremos 5 comparaciones para encontrar lo que estamos buscando, ya que el árbol solo ha crecido un nivel más profundo cuando multiplicamos la cantidad de datos. Como resultado, la complejidad del algoritmo se puede describir como un orden logarítmico.

Trazando log(n) en una hoja de papel simple, dará como resultado un gráfico donde el aumento de la curva se desacelera n aumenta:

O(log n)


509
2018-02-21 22:22



O(log N) Básicamente significa que el tiempo aumenta linealmente mientras el n sube exponencialmente Entonces si toma 1 segundo para calcular 10 elementos, tomará 2 segundos para calcular 100 elementos, 3 segundos para calcular 1000 elementos, etc.

Es O(log n) cuando dividimos y conquistamos el tipo de algoritmos, por ejemplo, la búsqueda binaria. Otro ejemplo es el ordenamiento rápido donde cada vez que dividimos el arreglo en dos partes y cada vez que se toma O(N) tiempo para encontrar un elemento pivote. Por lo tanto N O(log N) 


463
2018-02-21 20:18



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

Árbol binario es un caso donde un problema de tamaño n se divide en un sub-problema de tamaño n / 2 hasta que se llega a un problema de tamaño 1:

height of a binary tree

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

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


196
2017-10-26 19:33



Si tuvieras una función que lleva:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Luego toma registro2(n) tiempo los Gran notación O, en términos generales, significa que la relación solo necesita ser verdadera para n grande, y que los factores constantes y los términos más pequeños pueden ignorarse.


120
2018-02-21 20:11



Visión de conjunto

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

En primer lugar, querrás tener una idea general del logaritmo, que puedes obtener de https://en.wikipedia.org/wiki/Logarithm . Uso de las ciencias naturales e y el registro natural. Los discípulos de ingeniería usarán log_10 (base de registro 10) y los científicos utilizarán log_2 (log base 2) mucho, ya que las computadoras están basadas en binarios. A veces verá abreviaturas de registro 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 mires los siguientes ejemplos de código, te recomiendo mirar O (1), luego O (n), luego O (n ^ 2). Después de que seas bueno con ellos, mira a los demás. He incluido ejemplos claros así como variaciones para demostrar cómo los cambios sutiles aún pueden dar como resultado 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 para hacer que otras. Estas categorías ayudan a darnos una forma de ordenar el rendimiento del algoritmo. Algunos crecen más rápido a medida que crece la entrada n. La siguiente tabla muestra dicho crecimiento numéricamente. En la tabla a continuación, piense en log (n) como el techo de log_2.

enter image description here

Ejemplos de código simple de varias categorías de 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 solo 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 muestra un algoritmo que se ejecuta en log_2 (n). Observe que la operación de publicación del bucle for multiplica el valor actual de i por 2, por lo que i va de 1 a 2 a 4 a 8 a 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 muestra log_3. darse cuenta i va del 1 al 3 al 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 siempre que el número sea mayor que 1 y el resultado se multiplique repetidamente contra sí mismo, verá 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 se imprime hola n veces.

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

Este algoritmo muestra una variación, donde se 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 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, lo que aún resulta en el resultado final 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 cuadrados Ejemplos:

  • Algoritmo 10

O(n^2) se obtiene fácilmente al anidar bucles estándar.

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 cubo 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";

Resumen

Lo anterior proporciona varios ejemplos directos y variaciones para ayudar a demostrar qué cambios sutiles pueden introducirse que realmente no cambian el análisis. Espero que te dé suficiente información.


107
2018-04-26 22:50



Tiempo de ejecución logarítmico (O(log n)) esencialmente significa que el tiempo de ejecución crece en proporción a la logaritmo del tamaño de entrada; como ejemplo, si 10 elementos requieren como máximo cierta cantidad de tiempo x, y 100 elementos toman como máximo, por ejemplo, 2x, y 10,000 artículos toman como máximo 4x, entonces se ve como un O(log n) complejidad del tiempo


84
2018-02-21 20:10



El logaritmo

Ok, probemos y entendamos completamente qué es un logaritmo en realidad.

Imagina que tenemos una cuerda y la hemos atado a un caballo. Si la cuerda está directamente atada al caballo, la fuerza que el caballo necesitaría para alejarse (por ejemplo, de un hombre) es directamente 1.

Ahora imagina que la cuerda está enrollada alrededor de un poste. El caballo para escaparse ahora tendrá que tirar muchas veces más duro. La cantidad de veces dependerá de la rugosidad de la cuerda y del tamaño del poste, pero supongamos que multiplicará la fuerza de uno por 10 (cuando la cuerda da un giro completo).

Ahora, si la cuerda se bucle una vez, el caballo tendrá que tirar 10 veces más duro. Si el humano decide hacerlo realmente difícil para el caballo, puede volver a enrollar la cuerda alrededor de un poste, aumentando su fuerza 10 veces adicionales. Un tercer bucle aumentará nuevamente la fuerza otras 10 veces.

enter image description here

Podemos ver que para cada bucle, el valor aumenta en 10. El número de vueltas requerido para obtener cualquier número se llama el logaritmo del número, es decir, necesitamos 3 mensajes para multiplicar su fuerza por 1000 veces, 6 mensajes para multiplicar su fuerza por 1,000,000.

3 es el logaritmo de 1,000, y 6 es el logaritmo de 1,000,000 (base 10).

Entonces, ¿qué significa realmente O (log n)? 

En nuestro ejemplo anterior, nuestra 'tasa de crecimiento' es O (log n). Por cada bucle adicional, la fuerza que puede soportar nuestra cuerda es 10 veces más:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Ahora el ejemplo anterior sí utilizó la base 10, pero afortunadamente la base del registro es insignificante cuando hablamos de notación grande o.

Ahora imaginemos que está tratando de adivinar un número entre 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Ahora te tomó 7 conjeturas para hacerlo bien. Pero, ¿cuál es la relación aquí? ¿Cuál es la cantidad más grande de elementos que puedes adivinar de cada conjetura adicional?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Usando el gráfico, podemos ver que si usamos una búsqueda binaria para adivinar un número entre 1-100 nos llevará a lo sumo 7 intentos. Si tuviéramos 128 números, también podríamos adivinar el número en 7 intentos, pero 129 números nos llevarán a lo sumo 8 intentos (en relación con los logaritmos, aquí necesitaríamos 7 conjeturas para un rango de valores de 128, 10 conjeturas para un rango de valores de 1024. 7 es el logaritmo de 128, 10 es el logaritmo de 1024 (base 2)).

Tenga en cuenta que he marcado 'a lo sumo'. La notación grande o siempre se refiere al peor caso. Si tienes suerte, puedes adivinar el número en un intento, por lo que el mejor caso es O (1), pero esa es otra historia.

Podemos ver que por cada conjetura nuestro conjunto de datos se está reduciendo. Una buena regla general para identificar si un algoritmo tiene un tiempo logarítmico es   para ver si el conjunto de datos se reduce en un cierto orden después de cada iteración

¿Qué hay de O (n log n)?

Eventualmente te encontrarás con un tiempo linearítmico O (n log (n) algoritmo. La regla de oro anterior se aplica nuevamente, pero esta vez la función logarítmica debe ejecutarse n veces, p. reduciendo el tamaño de una lista n veces, que ocurre en algoritmos como un mergesort.

Puede identificar fácilmente si el tiempo algorítmico es n log n. Busque un bucle externo que recorre una lista (O (n)). Luego mira si hay un bucle interno. Si el lazo interno es cortar / reducir el conjunto de datos en cada iteración, ese ciclo es (O (log n), y así el algoritmo total es = O (n log n).

Descargo de responsabilidad: El ejemplo del logaritmo de cuerda fue tomado del excelente Libro del Matemático del Deleite de W.Sawyer. 


55
2017-10-08 14:27



Puedes pensar en O (log N) intuitivamente diciendo que el tiempo es proporcional al número de dígitos en N.

Si una operación realiza un trabajo de tiempo constante en cada dígito o bit de una entrada, toda la operación llevará tiempo proporcional al número de dígitos o bits en la entrada, no a la magnitud de la entrada; por lo tanto, O (log N) en lugar de O (N).

Si una operación realiza una serie de decisiones de tiempo constante, cada una de las cuales (reduce por un factor de 3, 4, 5 ..) el tamaño de la entrada a considerar, el todo tomará un tiempo proporcional a la base de registro 2 (base 3 , base 4, base 5 ...) del tamaño N de la entrada, en lugar de ser O (N).

Y así.


54
2018-02-21 20:13



La mejor manera en la que siempre he tenido que visualizar mentalmente un algoritmo que se ejecuta en O (log n) es la siguiente:

Si aumenta el tamaño del problema en una cantidad multiplicativa (es decir, multiplica su tamaño por 10), el trabajo solo se incrementará en una cantidad aditiva.

Aplicando esto a su pregunta de árbol binario para que tenga una buena aplicación: si duplica el número de nodos en un árbol binario, la altura solo aumenta en 1 (una cantidad aditiva). Si lo duplicas nuevamente, aún así solo aumentó en 1. (Obviamente supongo que se mantiene equilibrado y tal). De esta forma, en lugar de duplicar tu trabajo cuando se multiplica el tamaño del problema, solo estás haciendo un poco más de trabajo. Es por eso que los algoritmos O (log n) son increíbles.


48
2018-02-22 19:51



Qué es el registrosegundo(norte)?

Es la cantidad de veces que puede cortar un registro de longitud n repetidamente en b partes iguales antes de llegar a una sección de tamaño 1.


33
2018-03-19 19:28