¿Qué significa exactamente O (log n)?
Estoy aprendiendo sobre los tiempos de ejecución y los tiempos amortizados de Big O Notation. Entiendo la noción de tiempo lineal O(n) , lo que significa que el tamaño de la entrada afecta proporcionalmente el crecimiento del algoritmo... y lo mismo ocurre, por ejemplo, con el tiempo cuadrático O(n 2 ), etc., incluso algoritmos , como los generadores de permutaciones, con O(n!) veces, que crecen mediante 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 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.
No puedo entender cómo identificar una función con un tiempo de registro.
Los atributos más comunes de la función de tiempo de ejecución logarítmica son los siguientes:
- la elección del siguiente elemento sobre el cual realizar alguna acción es una de varias posibilidades, y
- sólo será necesario elegir uno.
o
- los elementos sobre los que se realiza la acción son dígitos de n
Esta es la razón por la que, por ejemplo, buscar personas en una guía telefónica es O(log n). No es necesario consultar a todas las personas en la guía telefónica para encontrar la correcta; en su lugar, puedes simplemente dividir y conquistar buscando según dónde está su nombre alfabéticamente, y en cada sección solo necesitas explorar un subconjunto de cada sección antes de encontrar el número de teléfono de alguien.
Por supuesto, una guía telefónica más grande todavía le llevará más tiempo, pero no crecerá tan rápidamente como el aumento proporcional del tamaño adicional.
Podemos ampliar el ejemplo de la guía telefónica para comparar otros tipos de operaciones y su tiempo de ejecución. Asumiremos que nuestra guía telefónica tiene empresas (las "Páginas Amarillas") que tienen nombres únicos y personas (las "Páginas Blancas") que pueden no tener nombres únicos. Un número de teléfono se asigna como máximo a una persona o empresa. También asumiremos que se necesita un tiempo constante para 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 más rápido a más lento:
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, busque el número de teléfono eligiendo un punto aleatorio aproximadamente 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 repite el proceso aproximadamente 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, busque la persona o empresa con ese número.
O(n log n): Hubo una confusión en la oficina de la imprenta y nuestra guía telefónica tenía todas las páginas insertadas en un orden aleatorio. Corrija el orden para que sea correcto mirando el nombre en cada página y luego colocando 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 imprenta. Las guías telefónicas están esperando ser enviadas por correo a cada residente o empresa, y hay una etiqueta en cada guía telefónica que identifica a dónde deben enviarse por correo. Cada persona o empresa recibe una guía telefónica.
O(n log n): queremos personalizar la guía telefónica, por lo que buscaremos el nombre de cada persona o empresa en su copia designada, luego rodearemos su nombre en la guía y escribiremos 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 blanqueador 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 debía cargar los libros se ha vuelto loco: ¡está colocando los libros en el camión en un orden aleatorio! Peor aún, carga todos los libros en el camión, luego comprueba si están en el orden correcto y, si no, los descarga y empieza 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 sus compañeros de trabajo le gasta 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 un duplicado 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 así tiene que cargar todos los libros originales y duplicados que se han impreso.
O(log N)Básicamente significa que el tiempo aumenta linealmente mientras que el ntiempo aumenta exponencialmente. Entonces, si se necesitan 1segundos para calcular 10elementos, se necesitarán 2segundos para calcular 100elementos, 3segundos para calcular 1000elementos, y así sucesivamente.
Es O(log n)cuando dividimos y venceremos el tipo de algoritmos, por ejemplo, la búsqueda binaria. Otro ejemplo es la clasificación rápida, en la que cada vez dividimos la matriz en dos partes y cada vez lleva O(N)tiempo encontrar un elemento pivote. De ahí que 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 muestra un árbol binario. Observe cómo cada nivel contiene el doble de nodos en comparación con el nivel anterior (por lo tanto, binario ):
La búsqueda binaria es un ejemplo complejo O(log n). Digamos que los nodos en el nivel inferior del árbol en la figura 1 representan elementos de alguna colección ordenada. La búsqueda binaria es un algoritmo de divide y vencerás, y el dibujo muestra cómo necesitaremos (como máximo) 4 comparaciones para encontrar el registro que estamos buscando en este conjunto de datos de 16 elementos.
Supongamos que, en cambio, tenemos un conjunto de datos con 32 elementos. Continúe con el dibujo de arriba para descubrir que ahora necesitaremos 5 comparaciones para encontrar lo que estamos buscando, ya que el árbol solo ha crecido un nivel más profundo cuando multiplicamos la cantidad de datos. Como resultado, la complejidad del algoritmo puede describirse como un orden logarítmico.
Trazarlo log(n)en una hoja de papel normal dará como resultado un gráfico en el que el ascenso de la curva se desacelera a medida que naumenta:
Descripció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 impresas 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 las ciencias naturales ey el registro natural. Los discípulos de ingeniería usarán mucho log_10 (log base 10) y los informáticos usarán log_2 (log base 2), ya que las computadoras están basadas en binarios. A veces verá abreviaturas de registro natural como ln(), los ingenieros normalmente dejan el _10 desactivado y solo usan log()y log_2 se abrevia como lg(). Todos los tipos de logaritmos crecen de manera similar, por eso comparten la misma categoría de log(n).
Cuando observa los ejemplos de código a continuación, recomiendo mirar O(1), luego O(n), luego O(n^2). Una vez que seas bueno con ellos, mira los demás. He incluido ejemplos claros y variaciones para demostrar cómo los cambios sutiles pueden dar como resultado 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 darnos una forma de ordenar el rendimiento del algoritmo. Algunos crecieron más rápido a medida que crece la entrada n. La siguiente tabla demuestra dicho crecimiento numéricamente. En la siguiente tabla, piense en log(n) como el límite máximo de log_2.
Ejemplos de código simple de varias categorías O grandes:
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, así es O(1).
print "hello";
- Algoritmo 2:
El algoritmo 2 imprime hola 3 veces, sin embargo, no depende del tamaño de entrada. Incluso a medida que n crece, este algoritmo siempre imprimirá hola solo 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: 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 ipasa 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: 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: 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, estamos ante 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 y 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. norte/2 = 1/2 * norte. 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 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, lo que aún da como resultado que el resultado final seaO(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 bucles for estándar.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
- Algoritmo 11
Como el algoritmo 10, pero con algunas variaciones.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O(n^3) - n al cubo Ejemplos:
- Algoritmo 12
Esto es como el algoritmo 10, pero con 3 bucles en lugar de 2.
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
print "hello";
- Algoritmo 13
Como el algoritmo 12, pero con algunas variaciones que aún dan resultados 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 sencillos 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.
La siguiente explicació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 se obtiene O(log n), que es la cantidad de trabajo que se debe realizar en el árbol anterior para llegar a una solución.
Un algoritmo común con complejidad temporal O(log n) es la búsqueda binaria, cuya relación recursiva es T(n/2) + O(1), es decir, en cada nivel posterior del árbol se divide el problema por la mitad y se realiza una cantidad constante de trabajo adicional.
