¿Qué significa exactamente O (log n)?

2140

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.

Andreas Grech
fuente
61
Un árbol binario de 1 nodo tiene altura log2 (1) +1 = 1, un árbol de 2 nodos tiene altura log2 (2) +1 = 2, un árbol de 4 nodos tiene altura log2 (4) +1 = 3, y pronto. Un árbol de n-nodos tiene altura log2 (n) +1, por lo que agregar nodos al árbol hace que su altura promedio crezca logarítmicamente.
David R Tribble
36
Una cosa que veo en la mayoría de las respuestas es que esencialmente describen "O (algo)" significa que el tiempo de ejecución del algoritmo crece en proporción a "algo". Dado que solicitó el "significado exacto" de "O (log n)", no es cierto. Esa es la descripción intuitiva de la notación Big-Theta, no Big-O. O (log n) intuitivamente significa que el tiempo de ejecución crece como máximo proporcionalmente a "log n": stackoverflow.com/questions/471199/…
Mehrdad Afshari
31
Siempre recuerdo dividir y conquistar como el ejemplo para O (log n)
RichardOD
14
Es importante darse cuenta de que es log base 2 (no base 10). Esto se debe a que en cada paso de un algoritmo, elimina la mitad de sus opciones restantes. En informática, casi siempre tratamos con la base de registro 2 porque podemos ignorar las constantes. Sin embargo, hay algunas excepciones (es decir, los tiempos de ejecución de Quad Tree son log base 4)
Ethan
13
@ Ethan: No importa en qué base se encuentre, ya que la conversión de bases es solo una multiplicación constante. La fórmula es log_b (x) = log_d (x) / log_d (b). Log_d (b) solo será una constante.
mindvirus

Respuestas:

2711

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 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 ha impreso.

John Feminella
fuente
81
@cletus: Casualmente, me temo. Lo elegí porque las guías telefónicas tienen una N grande, las personas entienden lo que son y lo que hacen, y porque es versátil como ejemplo. Además, ¡tengo que usar robots en mi explicación! Una victoria completa. (Además, ¡parece que tu respuesta se hizo antes de que incluso fuera miembro de StackOverflow para empezar!)
John Feminella
12
"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. Elimine un poco de blanco y elimine cada cero". <- este no es el orden N al cuadrado. N se define como el tamaño de la entrada. El tamaño de la entrada es el número de números de teléfono, que es el número de números por libro multiplicado por el número de libros. Eso sigue siendo una operación de tiempo lineal.
Billy ONeal
21
@Billy: en este ejemplo, Nes el número de personas en un solo libro. Debido a que cada persona en la guía telefónica también obtiene su propia copia del libro, hay guías telefónicas N idénticas , cada una con Npersonas, que es O (N ^ 2).
John Feminella
48
¿No es O (1) el mejor caso, en lugar del peor de los casos, ya que extrañamente se destaca como?
Svip
54
Me tomó tiempo O (long⅝n! N-55/2) encontrar una definición O (log n) que finalmente tenga sentido. +1
iAteABug_And_iLiked_it
611

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)

fastcodejava
fuente
109
Tres líneas de sabiduría que superan a todas las demás respuestas de ensayos ... :) En caso de que alguien se lo pierda, en el contexto de la programación, la base del registro es 2 (no 10), por lo que O (log n) escala como 1 segundo durante 10 elementos, 2 segundos por 20, 3 por 40 etc.
nawfal
3
De acuerdo, conciso y claro, aunque la pregunta final del OP fue cómo identificar una función logarítmica, no exactamente "qué es"
Adam
44
Sí, la función logarítmica es inversa a la función exponencial. ((log x) base a) es inversa de (una potencia x). El análisis cualitativo de estas funciones con gráficos daría más intuición.
intercambio excesivo
77
Esto me llevó alrededor de 3 lecturas para darme cuenta de que no estaba mal. El tiempo sube linealmente, mientras que el número de elementos es exponencial. Esto significa más elementos durante menos tiempo . Esto es mentalmente agotador para aquellos que visualizan logcomo la curva de registro familiar en un gráfico.
Qix - MONICA FUE MALTRATADA
1
Creo que esta es una muy buena respuesta, excepto por la parte en la que afirma que la búsqueda binaria es un algoritmo de divide y vencerás. No lo es
code_dredd
579

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 ):

Árbol 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:

O (log n)

Jørn Schou-Rode
fuente
6060
"Observe cómo cada nivel contiene el doble número de nodos en comparación con el nivel anterior (por lo tanto, binario)" Esto es incorrecto. Lo que estás describiendo es un árbol binario equilibrado . Un árbol binario solo significa que cada nodo tiene como máximo dos hijos.
Oenotria
8
De hecho, es un árbol binario equilibrado muy especial, llamado árbol binario completo. He editado la respuesta pero necesito que alguien la apruebe.
user21820
55
Un árbol binario completo no necesita tener el último nivel para estar completamente lleno. Yo diría que un "árbol binario completo" es más apropiado.
Sr. AJ
Su respuesta intenta responder más concretamente al problema original del OP, por lo que es mejor que la respuesta aceptada actual (IMO), pero aún es muy incompleta: solo da un medio ejemplo y 2 imágenes ...
nbro
2
Este árbol tiene 31 elementos, no 16. ¿Por qué se llama un conjunto de datos de 16 elementos? Cada nodo en él representa un número, de lo contrario sería un árbol binario ineficiente: P
Perry Monschau
245

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:

altura de un árbol binario

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.

2cupsOfTech
fuente
2
novato aquí. Entonces, ¿podría decir que la altura del árbol es la tasa de división por recursión para alcanzar el tamaño n = 1?
Cody
@Cody, sí, en su mayor parte su observación es precisa. Este ejemplo ilustra / utiliza log_2. Su observación pasaría más allá log_2y sería precisa para cualquier log_xlugar x > 1. Sin embargo, hacer una división recta no puede conducir a 1 exactamente, por lo que es posible que desee decir la división recursiva hasta que Ceiling()la última división sea igual a 1, o algo similar.
James Oravec
199

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.

ingrese la descripción de la imagen aquí

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.

James Oravec
fuente
17
Increíble. La mejor explicación para mí que he visto. Sería mejor si O(n^2)se nota como una combinación de O(n)y O(n), entonces O(n) * O(n) = O(n * n) = O(n^2). Se siente como saltar un poco sin esta ecuación. Esta es una repetición de una explicación previa, pero creo que esta repetición puede proporcionar más confianza a los lectores para comprender.
Eonil
2
Esta es simplemente la mejor explicación.
Edgar Kiljak
2
@IceTea, para darle una idea / intuición a su pregunta. Si trazas un gráfico nversus n/2verás que ambos forman una línea recta. Esto los coloca en la misma clase ya que tienen tasas de crecimiento similares (piense en ello como la forma de los gráficos). Del mismo modo, si trazó un gráfico log_2versus log_3verá que ambos toman "formas similares" o "tasas de crecimiento similares".
James Oravec
1
@IceTea, la explicación dada por @Shai y @James es más precisa, n/2 or 2n or n+2 or ntendrá una línea diferente en el gráfico pero tendrá la misma tasa de crecimiento, lo que significa que todos seguirán un crecimiento lineal.
Naresh Joshi el
2
¿Qué tal el caso en el que tenemos dos bucles anidados, pero el segundo iterador depende del primero? ¿Esta dependencia afecta la complejidad del tiempo?
Bionix1441
131

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 2 (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.

Mark Byers
fuente
¿es log2 (n) lo mismo que o (log n)?
Sven van den Boogaart
Sí, vea el comentario de nawfal para obtener otra respuesta aquí: (copiar y pegar): en el contexto de la programación, la base del registro es 2 (no 10), por lo que O (log n) escala como 1 segundo para 10 elementos, 2 segundos para 20 , 3 por 40, etc.
Andrejs
@SvenvandenBoogaart, ilustra el ejemplo en esta solución log_2, que está en la clase O(log(n)). Hay muchos otros en la misma clase, O(log(n))es decir, log_xdóndex > 1
James Oravec, el
@Andrejs, tu comentario so O(log n) scales like 1 sec for 10 elements, 2 sec for 20, 3 for 40 etces inexacto. Ese patrón / clase coincidiría / se alinearía con O(n)no O(log(n)). Si a alguien le interesara log_10, un ejemplo equivalente sería 1 segundo para 10 elementos, 2 segundos para 100, 3 para 1000, etc.
James Oravec,
99

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.

Luego.
fuente
1
+1, pero realmente deberías señalar que es log2, no log10.
Adriano Varoli Piazza
6262
log2 o log10 es irrelevante. Solo difieren en un factor de escala, lo que los hace del mismo orden, es decir, todavía crecen al mismo ritmo.
Noldorin
17
Lo divertido de los logaritmos es que, al comparar alturas relativas, no importa la base exacta que uses. log 10,000 / log 100es 2 independientemente de la base que use.
Anon
12
Para ser quisquilloso, O (lg n) significa que el tiempo de ejecución es como máximo proporcional a lg n. Lo que usted describe es Theta (lg n).
1
@rgrig: Eso es cierto. He editado algunos "en el mosts" para indicar la naturaleza de límite superior de big-O.
Anon
95

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.

ingrese la descripción de la imagen aquí

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 .

benscabbia
fuente
No. In our example above, our 'growth rate' is O(log n). For every additional loop, the force our rope can handle is 10 times more, respaldado por un gráfico que muestra n == número de bucles y our 'growth rate'=> 10 ^ n, que NO es log n. El ejemplo se puede corregir haciendo n=# horses, lo que requiere restringir los bucles log n. Los malos ejemplos pedagógicos producen estudiantes que solo creen que entienden.
psimpson
56

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í.

sombra de Luna
fuente
77
Creo que lo suficientemente preciso y más fácil de entender que la mayoría de las explicaciones.
T.
es una explicación de log<sub>10</sub> N, ¿verdad?
LiuYan 刘 研
1
@LiuYan 刘 研 no dijeron en qué base estaba el número de dígitos. Sin embargo, en cualquier caso, log₂ (n) = log₁₀ (n) / log₁₀ (2) y 1 / log₁₀ (2) es, por lo tanto, un multiplicador constante, con el mismo principio aplicable a todas las demás bases. Esto muestra dos cosas. En primer lugar, el principio de la sombra de la luna se aplica independientemente de la base (aunque cuanto más baja sea la base, menos "jags" en la estimación) y también que O (log n) es O (log n) sin importar la base del cálculo que lo llevó a esa conclusión .
Jon Hanna
"proporcional" ... "cada uno de los cuales reduce a la mitad el tamaño de la entrada" ??????
csguy
52

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.

DivinoWolfwood
fuente
52

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 .

Aquí hay algunas funciones y sus complejidades esperadas

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

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

Analizando el tiempo de ejecución de un programa

Teoman shipahi
fuente
55
No pondría O (n log n) en la cesta mala . Pertenece al justo .
André Werlang
Al ver el cuadro de complejidad big-O (arriba), debe recordar que O (n) es un punto lineal real, no el borde rosa / naranja. @Andre Es por eso que O (n log n) está marcado correctamente en el soporte de rendimiento 'malo', es peor rendimiento que lineal.
JavaBeast
@JavaBeast correcto, mientras que el rendimiento de O (n log n) es técnicamente peor que O (n), consulte la tabla anterior, que presenta una buena comparación de ellos (ver el crecimiento de los dos). otoh el gráfico, de una fuente diferente, es contradictorio porque pone O (1) y O (log n) en el mismo bien / excelente. su orden relativo de crecimiento es comparable a O (n) y O (n log n). tl; dr; O (n log n) no es excelente, pero está lejos de ser malo.
André Werlang
1
Esta respuesta es incorrecta! Se supone que N = N * N. De hecho, N = N! Su ejemplo es en realidad N al cubo. Haces lo mismo en tu gráfico. Su O (n) en realidad debería ser la división entre horrible y malo. Prueba matemática: dices que for loop es constante con O (1). Eso es lo que realmente significa el 1, no depende de N. Simplemente significa que no es variable. Pero es variable ya que depende de N. Dos veces N y la mitad del tiempo. Por lo tanto, no es válido. Si es de ese libro, ¡no lo compres! El gráfico de código que has mostrado no es real, es una broma, mira "Theesome", ¡significa que tres personas tienen sexo al mismo tiempo! OMG
jgmjgm
1
¿No debería O (n) estar en la diagonal?
gyosifov
46

¿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.

Chad Brewbaker
fuente
Excelente comentario! Es conciso y exactamente la respuesta que busco.
DennisL
18

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.

David Kanarek
fuente
2
¿Por qué es log base 2? En la selección rápida aleatoria, por ejemplo, no creo que sea la base 2. Hasta donde sé, la base no importa, ya que la base de registro a (n) = log2 (n) / log2 (a), por lo que cada logaritmo es diferente de otra por una constante, y las constantes se ignoran en notación big-o. De hecho, escribir la base de un registro en notación big-o es un error en mi opinión, ya que está escribiendo una constante.
IVlad
Es muy cierto que se puede convertir a cualquier base y no importa, pero si está tratando de obtener el rendimiento Big-O y ve la reducción constante a la mitad, ayuda a comprender que no verá la base de registro 10 reflejada en el código.
David Kanarek
Un aparte: en cosas como los árboles B, donde los nodos tienen un despliegue de más de 2 (es decir, "más ancho" que un árbol binario), todavía verá el crecimiento O (logn), porque todavía está dividido y -conquistar, pero la base del registro estará relacionada con el despliegue.
Roger Lipscombe
La digresión en el registro 2 fue bastante útil, en realidad.
Dan Rosenstark
15

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

usuario2421873
fuente
3
+1 por mencionar "El logaritmo es esencialmente el inverso de la exponenciación".
talonx
12

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);
    }
Ravi Bisla
fuente
Estoy seguro de que me falta algo, pero ¿no sería siempre cero y los bucles se ejecutan para siempre en ambos casos, ya que 0 * 2 = 0 y 0/2 = 0?
dj_segfault
2
@dj_segfault, ese fue mi error. Creo que ahora tiene sentido ... :)
Ravi Bisla
@RaviBisla Otras respuestas indican que una entrada de 10 tomaría 1 vez tanto como 10 bucles, y una entrada de 100 tomaría 3 veces el tiempo de entrada de 1, que definitivamente no es el caso con esos ejemplos. stackoverflow.com/a/2307330/1667868
Sven van den Boogaart
12

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

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

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

stmax
fuente
44
O (log n) tiene el mismo orden que O (ld n) u O (LN n). Son proporcionales Entiendo que para aprender es más fácil usar ld.
helios
44
"más precisamente es O (ld n)" - No, no lo es: todos los registros son del mismo orden (cada uno difiere de los demás solo por algún factor de escala constante, que se ignora / ignora).
ChrisW
1
tienes razón Chris, muy mala redacción. debería haberlo dicho como lo hizo helios. ayuda para aprender / comprender, pero finalmente todos los registros son del mismo orden.
stmax
10

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.

Azul platino
fuente
La nota final * resolvió mi confusión sobre los logaritmos basados ​​en 2 o 10 :) Muchas gracias.
Yahya
9

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.

Valentin Rocher
fuente
9

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

Brian R. Bondy
fuente
2
Esta respuesta es muy imprecisa. En primer lugar, puede pensar en reducir el trabajo a la mitad solo en el caso del logaritmo en la base 2. Es realmente increíble cómo esta respuesta (y la mayoría de las respuestas a la pregunta original) recibió tantos votos positivos. "(Asintóticamente equivalente a tercero, cuarto, ...)"? ¿Por qué responder una pregunta si no tienes tiempo?
nbro
8

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.

Hadewijch Debaillie
fuente
7

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".

ChrisW
fuente
Eso está mal. en.wikipedia.org/wiki/…
Michael Graczyk
7

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.

SPIRiT_1984
fuente
6

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

Ely
fuente
6

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)

Dinaiz
fuente
2
Hasta que algún malware comience a insertar una nueva lista con longitud x en dos niveles antes de que salgan los nodos. Entonces parecerá ser un ciclo infinito ...
Francis Cugler
1
No recibí tu comentario. ¿Mi explicación es incorrecta?
Dinaiz
1
Solo estaba haciendo una broma hipotética. Realmente no quería decir nada con eso.
Francis Cugler
6

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.

Sanjay Kumar
fuente
5

Árbol

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)

Khaled.K
fuente
5

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)

bruziuz
fuente
4

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.

Amirshk
fuente
gracias por el ejemplo Dice claramente cómo nuestro algoritmo puede usar el tiempo logarítmico en el método de dividir y conquistar.
Abc
Entonces, si es un bucle de n / 2, ¿siempre es log (n)?
Gil Beyruth
3

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.

mickeymoon
fuente
por favor editar tiene "O (n) o theta (n)" en ambos escenarios ...? Además, he escuchado mucho esto, el tamaño frente a los # dígitos. ¿Estamos diciendo size === 128 para n = 10000000 y dígitos === 8 para n = 10000000? Por favor aclarar.
Cody
2

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/

Kiriloff
fuente