time complexity - notacion - ¿Qué significa O(log n) exactamente?

notacion big o ejemplos (30)

¿Qué es log _b (n)?

Es el número 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.

Actualmente estoy aprendiendo sobre los tiempos de ejecución de Big O Notation y los tiempos amortizados. Entiendo la noción de O (n) 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 O (n ² ) etc., incluso los algoritmos , tales como 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); }

De manera similar, 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 de tiempo de ejecución logarítmico 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.

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

Por esta razón, por ejemplo, buscar personas en una guía telefónica es O (log n). No necesita consultar a cada persona en la guía telefónica para encontrar la correcta; en su lugar, simplemente puede dividir y conquistar al buscar en función de dónde está alfabéticamente su nombre, 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 y personas únicas (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 supondremos que lleva un 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 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) (caso promedio): dada la página donde está el nombre de una persona y su nombre, encuentre el número de teléfono.
O (registro n): dado el nombre de una persona, busque el número de teléfono seleccionando un punto al azar 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 para el nombre de una persona.)
O (n): encuentre a todas las personas cuyos números de teléfono contengan 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 de manera que sea correcto mirando el primer nombre en cada página y luego coloque esa página en el lugar apropiado en una guía telefónica nueva y vacía.

Para los siguientes ejemplos, 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 etiqueta en cada agenda que identifica dónde se debe enviar por correo. Cada persona o negocio obtiene una guía telefónica.

O (n log n): Queremos personalizar la guía telefónica, por lo tanto, vamos a encontrar el nombre de cada persona o empresa en su copia designada, luego rodear con un círculo su nombre en la agenda y escribir una breve nota de agradecimiento por su patrocinio .
O (n ² ): Ocurrió 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. Tomar un poco de blanco y eliminar cada cero.
O (n · n!): Estamos listos para cargar las agendas 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 comienza de nuevo. (Este es el temido tipo bogo ).
O (n ⁿ ): arreglas el robot para que esté cargando las cosas correctamente. Al día siguiente, uno de sus compañeros de trabajo le dedica una broma y conecta el robot del muelle de carga a los sistemas de impresión automatizados. ¡Cada vez que el robot carga un libro original, la impresora de fábrica ejecuta 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 cada libro original y duplicado que se haya impreso.

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

Lo reformularía 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 avanzando 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, eso es un algoritmo de tiempo logarítmico.

Para el ejemplo de árbol, puede ver fácilmente que reducir un nivel de nodos reduce un número exponencial de elementos a medida que continúa recorriendo. El ejemplo popular de buscar en una guía telefónica ordenada por nombres es esencialmente equivalente a atravesar un árbol de búsqueda binario (la página del medio es el elemento raíz, y puede deducir en cada paso si ir hacia la izquierda o hacia la derecha).

Pero que es exactamente O (log n)

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

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

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

En términos sencillos, 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 cuáles sean los valores de las constantes a, b, c y no d cero, 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 O de bit: significa "cuál es el orden del término dominante para cualquier n suficientemente grande".

El tiempo de ejecución logarítmico ( O(log n) ) significa esencialmente 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 cierta cantidad de tiempo x , y 100 elementos toman como máximo, por ejemplo, 2x , y 10,000 elementos toman como máximo 4x , luego se ve como una complejidad de tiempo O(log n) .

La explicación a continuación es usar 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 donde un problema de tamaño n se divide en un subproblema de tamaño n / 2 hasta que alcanzamos un problema de tamaño 1:

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

Un algoritmo común con complejidad de tiempo O (log n) es la búsqueda binaria 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 realiza una cantidad constante de trabajo adicional.

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

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

Aplicando esto a su pregunta sobre el á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 vuelves a duplicar, solo aumentará en 1. (Obviamente, asumo que se mantiene equilibrado y demás). 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 impresionantes.

Los algoritmos de logn y conquistar generalmente tienen un componente logn para el tiempo de ejecución. Esto viene de la repetición de la mitad de la entrada.

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

Edición: Como se señaló, la base de registro no importa, pero cuando se deriva el rendimiento Big-O de un algoritmo, el factor de registro provendrá de la mitad, por lo tanto, pienso en ello como base 2.

Primero te recomiendo leer el siguiente libro;

Algoritmos (4ª Edición)

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

Siguiendo el gráfico de complejidad de 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 un programa.

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

Puede 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 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 constantes, cada una de las cuales reduce a la mitad (se reduce en un factor de 3, 4, 5 ..) el tamaño de la entrada a considerar, la totalidad tomará un tiempo proporcional al log base 2 (base 3 , base 4, base 5 ...) del tamaño N de la entrada, en lugar de ser O (N).

Y así.

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.

Entonces toma log ₂ (n) tiempo. La notación Big O , en términos generales, significa que la relación solo debe ser cierta para n grande, y que se pueden ignorar factores constantes y términos más pequeños.

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 representa un árbol binario. Observe cómo cada nivel contiene el doble 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 dividir y conquistar, y el dibujo muestra cómo necesitaremos (a lo sumo) 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 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 cuando multiplicamos la cantidad de datos. Como resultado, la complejidad del algoritmo se puede describir como un orden logarítmico.

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

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

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

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 normalmente lo consideraría), su función crece linealmente.

O(log n)los tiempos de ejecución son muy comunes en cualquier tipo de aplicación de dividir y conquistar, porque usted (idealmente) está cortando 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 el tiempo aumenta más lentamente que O(log n)), entonces su función completa lo es O(log n). Es bastante común que cada paso requiera un 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 está ignorando la mitad de su entrada en cada paso posterior al dividir la matriz en la mitad y solo enfocarse 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 averiguar qué hacer a continuación, independientemente de qué tan grande sea la matriz que esté considerando en cualquier momento. Así que haces aproximadamente los pasos log (n) / log (2).

La complejidad del tiempo de ejecución de la ordenación de mezcla 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 da como resultado un total de aproximadamente los pasos log (n) / log (2). Sin embargo, en cada paso debe realizar operaciones de combinación en todos los elementos (ya sea una operación de combinación en dos sublistas de n / 2 elementos, o dos operaciones de combinación en cuatro sublistas de n / 4 elementos, es irrelevante porque agrega a tener que hacer esto para n elementos en cada paso). Así, 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 base para logaritmos, la única diferencia entre logaritmos de diferentes bases es un factor constante.

El logaritmo

Ok, tratemos de entender 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 palo. El caballo que se aleje ahora tendrá que tirar muchas veces más fuerte. La cantidad de veces dependerá de la rugosidad de la cuerda y del tamaño del palo, pero supongamos que multiplicará la fuerza de uno por 10 (cuando la cuerda haga un giro completo).

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

Podemos ver que para cada bucle, el valor aumenta en 10. El número de turnos necesarios para obtener cualquier número se denomina 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 O (log n) realmente?

En nuestro ejemplo anterior, nuestra ''tasa de crecimiento'' es O (log n) . Por cada bucle adicional, la fuerza que nuestra cuerda puede manejar 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 usó la base 10, pero afortunadamente la base del registro es insignificante cuando hablamos de gran notación.

Ahora imaginemos que estás 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 estimación 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 y 100, nos llevará un máximo de 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 a 8 intentos (en relación con los logaritmos, aquí necesitaríamos 7 intentos para un rango de valor de 128, 10 intentos para un rango de valor de 1024 .7 es el logaritmo de 128, 10 es el logaritmo de 1024 (base 2)).

Tenga en cuenta que he negrita "a lo sumo". La notación grande siempre se refiere al caso peor. Si tiene suerte, puede adivinar el número en un intento y el mejor caso es O (1), pero esa es otra historia.

Podemos ver que para cada conjetura nuestro conjunto de datos se está reduciendo. Una buena regla empírica 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 O (n n logaritmo) de tiempo lineal. La regla de oro anterior se aplica de nuevo, pero esta vez la función logarítmica debe ejecutarse n veces, por ejemplo, reducir el tamaño de una lista n veces , lo que ocurre en los algoritmos como un mergesort

Puede identificar fácilmente si el tiempo algorítmico es n log n. Busque un bucle externo que recorra 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 cuerdas se tomó del excelente libro Delicia matemática de W.Sawyer .

Visión general

Otros han dado buenos ejemplos de diagramas, como los diagramas de árbol. No vi ningún ejemplo de código simple. Así que 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á tener una idea general de logaritmo, que puede obtener de https://en.wikipedia.org/wiki/Logarithm . Las ciencias naturales utilizan e y el registro natural. Los discípulos de ingeniería usarán log_10 (log base 10) y los científicos de computación usarán log_2 (log base 2) mucho, ya que las computadoras tienen una base binaria. A veces verá abreviaturas de log natural como ln() , los ingenieros normalmente dejan el _10 apagado y solo usan log() y log_2 se abrevia como lg() . Todos los tipos de logaritmos crecen de manera similar, es por eso que comparten la misma categoría de log(n) .

Cuando mire los ejemplos de código a continuación, recomiendo mirar O (1), luego O (n) y 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.

Puede 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 crecen más rápido a medida que crece la entrada n. La siguiente tabla muestra 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 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 a medida que n crece, este algoritmo 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 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 voy 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. Noten que 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 mientras el número sea mayor que 1 y el resultado se multiplique repetidamente contra sí mismo, se 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 veces.

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

Algoritmo 7

Este algoritmo muestra una variación, donde se imprimirá hello 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) . El anidamiento de los bucles for nos ayuda a obtener la 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 todavía resulta en 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 cuadrados Ejemplos:

Algoritmo 10

O(n^2) se obtiene fácilmente anidando el estándar para los 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 ejemplos en cubos:

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 brinda varios ejemplos directos y variaciones para ayudar a demostrar qué cambios sutiles pueden introducirse que realmente no cambian el análisis. Esperemos que te da suficiente visión.

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 hits: 6, 3 luego 4. Y log2 12 = 3, lo cual es un buen porcentaje de cuántos hits donde sea necesario.

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 que alcance las listas de tamaño 1 (las hojas).

En el primer paso, divide por 2. Luego tienes 2 listas (2 ^ 1), divides cada una por 2, así que tienes 4 listas (2 ^ 2), divides otra vez, tienes 8 listas (2 ^ 3) ) y así sucesivamente hasta que el tamaño de tu lista sea 1

Eso te da la ecuación:

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

(se toma el lg de cada lado, siendo lg la base de registro 2)

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.

Y parece que esta notación fue mayoritariamente tomada 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 tratados aquí, propongo que los miembros de SIGACT, y los editores de las revistas de ciencias de la computación y matemáticas, adopten las anotaciones tal como se definieron anteriormente, a menos que se pueda encontrar una alternativa mejor 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 usaba para significar "C * g (n)> f (n)> 0".

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

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); }

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

Eso significa que en el bucle 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 se realizan 10 iteraciones. Esto se debe a que el paso en el bucle crece exponencialmente y, por lo tanto, toma solo 10 iteraciones para alcanzar 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 el exponencial crece muy rápido, entonces el logaritmo crece (inversamente) muy lento.

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

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

Imagina una colina muy alta con una base muy ancha 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 el tiempo lineal O (n), la segunda es O (log n).
Imagine un algoritmo, que acepta un entero, ncomo entrada y se completa en tiempo proporcional a nentonces es O (n) o theta (n) pero si se ejecuta en proporción proporcional al tiempo number of digits or the number of bits in the binary representation on number, el algoritmo se ejecuta en O (log n) o theta (log n) tiempo.

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

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

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 por un solo camino en el árbol ~ O (d) = O (registro n a base M)

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

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 su lugar, tomamos el tamaño de entrada como parámetro porque cualquiera que sea el código, la entrada es la misma. Así que el tiempo de ejecución es una función del tamaño de entrada.

A continuación se muestra un ejemplo de algoritmo de tiempo lineal.

Búsqueda lineal
Dados los n elementos de entrada, para buscar un elemento en la matriz que necesita como máximo ''n'' comparaciones . En otras palabras, no importa qué lenguaje de programación use, qué estilo de codificación prefiere, en qué sistema lo ejecuta. 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 veces el tamaño de entrada n.

A medida que aumenta el tamaño de entrada, aumenta el trabajo realizado (en este caso, el tiempo de ejecución) (por lo tanto, proporcionalidad)

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

Ver a medida que aumenta el tamaño de la 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.

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

Me gustaría agregar que la altura del árbol es la longitud de la ruta más larga desde la raíz a una hoja, y que la altura de un nodo es la longitud de la ruta más larga desde ese nodo a una hoja. La ruta significa el número de nodos que encontramos al atravesar el árbol entre dos nodos. Para lograr una complejidad de tiempo O (log n), el árbol debe estar equilibrado, lo que significa que la diferencia de altura entre los hijos de cualquier nodo debe ser menor o igual a 1. Por lo tanto, los árboles no siempre garantizan una complejidad de tiempo O (log n), a menos que estén equilibrados. En realidad, en algunos casos, la complejidad del tiempo de búsqueda en un árbol puede ser O (n) en el peor de los casos.

Puedes echar un vistazo a los árboles de equilibrio como AVL tree. Éste funciona para equilibrar el árbol mientras inserta datos para mantener una complejidad de tiempo de (registro n) mientras se busca en el árbol.

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 balanceado es O (registro ₂ n), ya que cada nodo tiene dos (note los "dos" como en el registro ₂ 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 (registro ₂ n) porque en cada paso se divide el espacio de búsqueda por 2.

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

Ahora, si puede probar, que en cada iteración de su algoritmo usted corta una fracción de este espacio, eso no es menos que algún límite, esto significa que su algoritmo se ejecuta en tiempo O (logN).

Debería señalar que estamos hablando 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 problemático. Pero la búsqueda binaria no es el único ejemplo. Supongamos que, de alguna manera, probaste que en cada paso tiras al menos 1/128 de espacio problemático. Eso significa que su programa todavía se está ejecutando a la hora O (logN), aunque es 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 utilizará varias variantes, y esto lleva al corte de alguna fracción en el espacio del problema.

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 el algoritmo de búsqueda binaria y la notación Big O para obtener más precisiones.