¿Qué significa exactamente O (log n)?

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 ² ), 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 ² ).

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 ₁₀ 100 = 2, pero no puedo entender cómo identificar una función con un tiempo logarítmico.

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:

• la elección del siguiente elemento en el que 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 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 se encuentra 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 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 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.

Estos son los tiempos de ejecución de algunas operaciones que podríamos realizar en la guía telefónica, de la más rápida a la más lenta:

• 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 ejemplos a continuación, ahora estamos en la oficina de la impresora. Las guías telefónicas están a la espera de ser enviadas por correo a cada residente o empresa, y hay una pegatina en cada guía telefónica que identifica a dónde deben enviarse. Cada persona o empresa 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 ² ): 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 ⁿ ): 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 ha impreso.

O(log N)básicamente significa que el tiempo sube linealmente mientras que nsube exponencialmente. Por lo tanto, si lleva 1segundos calcular los 10elementos, tardará 2segundos en calcular los 100elementos, 3segundos en calcular los 1000elementos, etc.

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

Ya se han publicado muchas buenas respuestas a esta pregunta, pero creo que realmente nos falta una importante: 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 ):

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 tenemos un conjunto de datos con 32 elementos. Continúe con el dibujo anterior para descubrir que ahora necesitaremos 5 comparaciones para encontrar lo que estamos buscando, ya que el árbol solo 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 naumenta:

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 subproblema de tamaño n / 2 hasta llegar a un problema de tamaño 1:

Y así es como obtienes 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 la complejidad del tiempo 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, divide el problema a la mitad y realiza una cantidad constante de trabajo adicional.

Visión general

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.

Primero, querrás tener una idea general del Logaritmo, que puedes obtener en https://en.wikipedia.org/wiki/Logarithm . Uso de la ciencia natural ey 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 registro natural ln(), ya que 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 mira los ejemplos de código a continuación, le 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 limpios, así como variaciones para demostrar cómo los cambios sutiles pueden 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 nos ayudan a ordenar el rendimiento del algoritmo. Algunos crecieron más rápido a medida que aumenta la entrada n. La siguiente tabla demuestra dicho crecimiento numéricamente. En la siguiente tabla, piense en log (n) como el techo de log_2.

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 así 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 lo 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). Observe que la operación posterior del bucle for multiplica el valor actual de i por 2, por lo que iva 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 demuestra log_3. El aviso iva 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 demostrar que, siempre que el número sea mayor que 1 y el resultado se multiplique repetidamente contra sí mismo, está observando 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 elO(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 dan 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 se pueden introducir que realmente no cambian el análisis. Esperemos que te dé suficiente información.

Si tenía una función que toma:

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 el tiempo log ₂ (n). La notación Big 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.

El tiempo de ejecución logarítmico ( O(log n)) esencialmente significa que el tiempo de ejecución aumenta en proporción al logaritmo del tamaño de entrada; por ejemplo, si 10 elementos toman como máximo una cantidad de tiempo x, y 100 artículos toman como máximo, digamos 2x, y 10,000 artículos toma como máximo 4x, luego parece una O(log n)complejidad de tiempo.

El logaritmo

Ok, intentemos comprender completamente lo que 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 imagine que la cuerda se enrolla alrededor de un poste. El caballo para escapar ahora tendrá que tirar muchas veces más fuerte. La cantidad de veces dependerá de la aspereza de la cuerda y el tamaño del poste, pero supongamos que multiplicará la fuerza por 10 (cuando la cuerda da una vuelta completa).

Ahora, si la cuerda se enrolla una vez, el caballo necesitará tirar 10 veces más fuerte. Si el humano decide hacer que sea realmente difícil para el caballo, puede enrollar la cuerda nuevamente alrededor de un poste, aumentando su fuerza en 10 veces más. Un tercer ciclo aumentará nuevamente la fuerza en 10 veces más.

Podemos ver que para cada bucle, el valor aumenta en 10. El número de vueltas requeridas para obtener cualquier número se llama logaritmo del número, es decir, necesitamos 3 publicaciones para multiplicar su fuerza por 1000 veces, 6 publicaciones 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 lazo adicional, la fuerza que puede manejar 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 utilizaba la base 10, pero afortunadamente la base del registro es insignificante cuando hablamos de notación grande.

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 hacer esto bien. ¿Pero cuál es la relación aquí? ¿Cuál es la mayor cantidad 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á como máximo 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 como máximo 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 en negrita 'a lo sumo'. La notación Big-O siempre se refiere al peor de los casos. Si tiene suerte, podría adivinar el número en un intento y, por lo tanto, 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 ver si el conjunto de datos se reduce en un cierto orden después de cada iteración

¿Qué pasa con O (n log n)?

Eventualmente se encontrará con un algoritmo de tiempo lineal lineal O (n log (n)) . La regla general anterior se aplica nuevamente, pero esta vez la función logarítmica tiene que ejecutarse n veces, por ejemplo, reduciendo el tamaño de una lista n veces , lo 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 itera a través de una lista (O (n)). Luego mira para ver si hay un bucle interno. Si el bucle interno está cortando / reduciendo el conjunto de datos en cada iteración, ese bucle es (O (log n)), por lo que el algoritmo general es = O (n log n) .

Descargo de responsabilidad: El ejemplo de logaritmo de cuerda fue tomado del excelente libro Mathematician's Delight de W.Sawyer .

Puede pensar en O (log N) intuitivamente al decir 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 tomará un 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 toma una serie de decisiones de tiempo constante, cada una de las cuales reduce a la mitad (reduce en un factor de 3, 4, 5 ..) el tamaño de la entrada a considerar, el conjunto 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í.

La mejor forma en 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, multiplique su tamaño por 10), el trabajo solo se incrementa 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 duplica nuevamente, solo aumentará en 1. (Obviamente, supongo que se mantiene equilibrado y tal). De esa manera, en lugar de duplicar su trabajo cuando se multiplica el tamaño del problema, solo está haciendo un poco más de trabajo. Es por eso que los algoritmos O (log n) son increíbles.

Primero te recomiendo que leas el siguiente libro;

Algoritmos (4ta Edición)

Aquí hay algunas funciones y sus complejidades esperadas. Los números indican frecuencias de ejecución de sentencias .

Siguiendo el cuadro de complejidad Big-O también tomado de bigocheatsheet

Por último, el escaparate muy simple que hay muestra cómo se calcula;

Anatomía de las frecuencias de ejecución de declaraciones de un programa.

Analizando el tiempo de ejecución de un programa (ejemplo).

¿Qué es el registro _b (n)?

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.

Los algoritmos de división y conquista generalmente tienen un logn componente en el tiempo de ejecución. Esto proviene de la reducción a la mitad de la entrada.

En el caso de la búsqueda binaria, cada iteración arroja la mitad de la entrada. Cabe señalar que en notación Big-O, log es log base 2.

Editar: como se señaló, la base de registro no importa, pero al derivar el rendimiento Big-O de un algoritmo, el factor de registro vendrá de la mitad, de ahí que piense en ello como base 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)?

Reformularía esto como 'la altura de un árbol binario completo es log n'. Calcular la altura de un árbol binario completo sería O (log n), si estuviera recorriendo paso a paso.

No puedo entender cómo identificar una función con un tiempo logarítmico.

El logaritmo es esencialmente el inverso de la exponenciación. Entonces, si cada 'paso' de su función está eliminando un factor de elementos del conjunto de elementos original, ese es un algoritmo de tiempo logarítmico.

Para el ejemplo del árbol, puede ver fácilmente que bajar un nivel de nodos reduce un número exponencial de elementos a medida que continúa atravesando. El ejemplo popular de mirar a través de una guía telefónica ordenada por nombre es esencialmente equivalente a recorrer un árbol de búsqueda binario (la página central es el elemento raíz, y puede deducir en cada paso si debe ir hacia la izquierda o hacia la derecha).

Estos 2 casos tomarán tiempo O (log n)

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) es un poco engañoso, más precisamente es O (log ₂ n), es decir (logaritmo con base 2).

La altura de un árbol binario equilibrado es O (log ₂ n), ya que cada nodo tiene dos (tenga en cuenta los "dos" como en log ₂ n) nodos secundarios. Entonces, un árbol con n nodos tiene una altura de log ₂ n.

Otro ejemplo es la búsqueda binaria, que tiene un tiempo de ejecución de O (log ₂ n) porque en cada paso divide el espacio de búsqueda por 2.

O(log n) se refiere a una función (o algoritmo, o paso en un algoritmo) que trabaja en una cantidad de tiempo proporcional al logaritmo (generalmente base 2 en la mayoría de los casos, pero no siempre, y en cualquier caso esto es insignificante por la notación big-O *) del tamaño de la entrada.

La función logarítmica es la inversa de la función exponencial. Dicho de otra manera, si su entrada crece exponencialmente (en lugar de linealmente, como lo consideraría normalmente), su función crece linealmente.

O(log n)los tiempos de ejecución son muy comunes en cualquier tipo de aplicación de divide y vencerás, porque (idealmente) estás reduciendo el trabajo a la mitad cada vez. Si en cada uno de los pasos de división o conquista, está haciendo un trabajo de tiempo constante (o un trabajo que no es de tiempo constante, pero con el tiempo creciendo más lentamente que O(log n)), entonces su función completa es O(log n). Es bastante común que cada paso requiera tiempo lineal en la entrada; esto equivaldrá a una complejidad de tiempo total de O(n log n).

La complejidad del tiempo de ejecución de la búsqueda binaria es un ejemplo de O(log n). Esto se debe a que en la búsqueda binaria, siempre ignora la mitad de su entrada en cada paso posterior al dividir la matriz por la mitad y solo se enfoca en la mitad con cada paso. Cada paso es de tiempo constante, porque en la búsqueda binaria solo necesita comparar un elemento con su clave para descubrir qué hacer a continuación, independientemente de cuán grande sea la matriz que está considerando en cualquier momento. Entonces, realiza aproximadamente los pasos log (n) / log (2).

La complejidad del tiempo de ejecución del tipo de fusión es un ejemplo de O(n log n). Esto se debe a que está dividiendo la matriz a la mitad con cada paso, lo que resulta en un total de aproximadamente log (n) / log (2) pasos. Sin embargo, en cada paso debe realizar operaciones de fusión en todos los elementos (ya sea una operación de fusión en dos sublistas de n / 2 elementos, o dos operaciones de fusión en cuatro sublistas de n / 4 elementos, es irrelevante porque se suma a tener que haz esto para n elementos en cada paso). Por lo tanto, la complejidad total es O(n log n).

* Recuerde que la notación big-O, por definición , las constantes no importan. También por el cambio de la regla de base para logaritmos, la única diferencia entre logaritmos de diferentes bases es un factor constante.

Simplemente significa que el tiempo necesario para esta tarea aumenta con log (n) (ejemplo: 2s para n = 10, 4s para n = 100, ...). Lea los artículos de Wikipedia sobre Algoritmo de búsqueda binaria y Big O Notation para obtener más precisiones.

En pocas palabras: en cada paso de su algoritmo puede reducir el trabajo a la mitad. (Asintóticamente equivalente a tercero, cuarto, ...)

Si traza una función logarítmica en una calculadora gráfica o algo similar, verá que se eleva muy lentamente, incluso más lentamente que una función lineal.

Esta es la razón por la cual los algoritmos con una complejidad de tiempo logarítmico son muy buscados: incluso para n realmente grande (digamos n = 10 ^ 8, por ejemplo), funcionan más que aceptablemente.

Pero, ¿qué es exactamente O (log n)

Lo que significa precisamente es "como ntiende hacia infinity, timetiende hacia a*log(n)donde ahay un factor de escala constante".

O en realidad, no significa eso en absoluto; lo más probable es que signifique algo así como " timedividido por a*log(n)tiende hacia 1".

"Tiende hacia" tiene el significado matemático habitual de 'análisis': por ejemplo, que "si elige cualquier constante arbitrariamente pequeña que no sea cero k, entonces puedo encontrar un valor correspondiente Xtal que ((time/(a*log(n))) - 1)sea ​​menor que kpara todos los valores nmayores que X".

En términos simples, significa que la ecuación para el tiempo puede tener algunos otros componentes: por ejemplo, puede tener un tiempo de inicio constante; pero estos otros componentes palidecen hacia la insignificancia para valores grandes de n, y a * log (n) es el término dominante para n grande.

Tenga en cuenta que si la ecuación fuera, por ejemplo ...

tiempo (n) = a + b log (n) + c n + d n n

... entonces esto sería O (n al cuadrado) porque, sin importar los valores de las constantes a, b, c, y no cero d, el d*n*ntérmino siempre dominaría sobre los demás para cualquier valor suficientemente grande de n.

Eso es lo que significa la notación bit O: significa "cuál es el orden del término dominante para cualquier n suficientemente grande".

Puedo agregar algo interesante, que leí en el libro de Kormen, etc., hace mucho tiempo. Ahora, imagine un problema, donde tenemos que encontrar una solución en un espacio problemático. Este espacio problemático debe ser finito.

Ahora, si puede probar, que en cada iteración de su algoritmo corta una fracción de este espacio, que es no menos de un límite, esto significa que su algoritmo se está ejecutando en tiempo O (logN).

Debo señalar que estamos hablando aquí de un límite de fracción relativa, no del absoluto. La búsqueda binaria es un ejemplo clásico. En cada paso, tiramos la mitad del espacio del problema. Pero la búsqueda binaria no es el único ejemplo de este tipo. Supongamos, de alguna manera, que demuestra que en cada paso tira al menos 1/128 del espacio del problema. Eso significa que su programa todavía se está ejecutando en tiempo O (logN), aunque significativamente más lento que la búsqueda binaria. Esta es una muy buena pista para analizar algoritmos recursivos. A menudo se puede demostrar que en cada paso la recursión no usará varias variantes, y esto conduce al corte de alguna fracción en el espacio del problema.

Puedo dar un ejemplo para un bucle for y tal vez una vez que capte el concepto, tal vez sea más fácil de entender en diferentes contextos.

Eso significa que en el ciclo el paso crece exponencialmente. P.ej

for (i=1; i<=n; i=i*2) {;}

La complejidad en la notación O de este programa es O (log (n)). Intentemos recorrerlo a mano (n está en algún lugar entre 512 y 1023 (excluyendo 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Aunque n está en algún lugar entre 512 y 1023, solo tienen lugar 10 iteraciones. Esto se debe a que el paso en el ciclo crece exponencialmente y, por lo tanto, solo se necesitan 10 iteraciones para llegar a la terminación.

El logaritmo de x (a la base de a) es la función inversa de a ^ x.

Es como decir que el logaritmo es el inverso de exponencial.

Ahora trate de verlo de esa manera, si la exponencial crece muy rápido, entonces el logaritmo crece (inversamente) muy lentamente.

La diferencia entre O (n) y O (log (n)) es enorme, similar a la diferencia entre O (n) y O (a ^ n) (un ser una constante).

En realidad, si tiene una lista de n elementos y crea un árbol binario a partir de esa lista (como en el algoritmo de dividir y conquistar), seguirá dividiendo por 2 hasta llegar a listas de tamaño 1 (las hojas).

En el primer paso, divide entre 2. Luego tiene 2 listas (2 ^ 1), divide cada una entre 2, por lo que tiene 4 listas (2 ^ 2), divide nuevamente, tiene 8 listas (2 ^ 3 ) y así sucesivamente hasta que el tamaño de su lista sea 1

Eso te da la ecuación:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(tomas el lg de cada lado, lg es la base de registro 2)

Cada vez que escribimos un algoritmo o código intentamos analizar su complejidad asintótica. Es diferente de su complejidad temporal .

La complejidad asintótica es el comportamiento del tiempo de ejecución de un algoritmo, mientras que la complejidad del tiempo es el tiempo de ejecución real. Pero algunas personas usan estos términos indistintamente.

Porque la complejidad del tiempo depende de varios parámetros, a saber.
1. Sistema físico
2. Lenguaje de programación
3. Estilo de codificación
4. Y mucho más ......

El tiempo de ejecución real no es una buena medida para el análisis.

En cambio, tomamos el tamaño de entrada como parámetro porque cualquiera que sea el código, la entrada es la misma. Entonces el tiempo de ejecución es una función del tamaño de entrada.

El siguiente es un ejemplo de Algoritmo de tiempo lineal

Búsqueda lineal
Dados n elementos de entrada, para buscar un elemento en la matriz que necesita en la mayoría de las comparaciones 'n' . En otras palabras, no importa qué lenguaje de programación use, qué estilo de codificación prefiera, en qué sistema lo ejecute. En el peor de los casos, solo requiere n comparaciones. El tiempo de ejecución es linealmente proporcional al tamaño de entrada.

Y no es solo una búsqueda, cualquiera que sea el trabajo (incremento, comparación o cualquier operación) es una función del tamaño de entrada.

Entonces, cuando dice que cualquier algoritmo es O (log n) significa que el tiempo de ejecución es log multiplicado por el tamaño de entrada n.

A medida que aumenta el tamaño de entrada, aumenta el trabajo realizado (aquí el tiempo de ejecución) (de ahí la proporcionalidad)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Vea a medida que aumenta el tamaño de entrada, aumenta el trabajo realizado y es independiente de cualquier máquina. Y si intenta averiguar el valor de las unidades de trabajo, en realidad depende de los parámetros especificados anteriormente. Cambiará de acuerdo con los sistemas y todo.

log x to base b = y es el inverso de b^y = x

Si tiene un árbol M-ario de profundidad d y tamaño n, entonces:

• atravesando todo el árbol ~ O (M ^ d) = O (n)

• Caminando un solo camino en el árbol ~ O (d) = O (log n a la base M)

En tecnología de la información significa que:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Ant parece que esta notación se tomó principalmente de las matemáticas.

En este artículo hay una cita: DE Knuth, "BIG OMICRON Y BIG OMEGA Y BIG THETA", 1976 :

Sobre la base de los temas discutidos aquí, propongo que los miembros de SIGACT, y los editores de revistas de informática y matemáticas, adopten las anotaciones como se definió anteriormente, a menos que se pueda encontrar una mejor alternativa razonablemente pronto .

Hoy es 2016, pero todavía lo usamos hoy.

En análisis matemático significa que:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Pero incluso en el análisis matemático a veces este símbolo se usó en el significado "C * g (n)> f (n)> 0".

Como sé por la universidad, el símbolo fue introducido por el matemático alemán Landau (1877-1938)

El ejemplo binario completo es O (ln n) porque la búsqueda se ve así:

1 2 3 4 5 6 7 8 9 10 11 12

La búsqueda de 4 produce 3 resultados: 6, 3 y luego 4. Y log2 12 = 3, que es una buena aproximación a la cantidad de resultados necesarios.

Si está buscando una respuesta basada en la intuición, me gustaría presentarle dos interpretaciones.

1. Imagine una colina muy alta con una base muy amplia también. Para llegar a la cima de la colina, hay dos formas: una es un camino dedicado que gira en espiral alrededor de la colina y llega a la cima, la otra: una pequeña terraza como esculturas cortadas para proporcionar una escalera. Ahora, si la primera forma es alcanzar en tiempo lineal O (n), la segunda es O (log n).

2. Imagine un algoritmo, que acepta un número entero, ncomo entrada y se completa en tiempo proporcional a nentonces es O (n) o theta (n) pero si se ejecuta en proporción de tiempo al number of digits or the number of bits in the binary representation on numberentonces el algoritmo se ejecuta en O (log n) o theta (log n) tiempo.

Los algoritmos en el paradigma Divide and Conquer son de complejidad O (logn). Un ejemplo aquí, calcula tu propia función de potencia,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

de http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/