¿Qué te dice realmente Big O?

Question

Hace dos días me sentí muy incómodo con la notación Big O. Ya he hecho dos preguntas:

1. ¿Por qué calcular el "Big O" si podemos calcular simplemente el número de pasos?
2. La idea principal de la notación Big O

Y ahora casi todo se ha aclarado. Pero hay algunas preguntas que todavía no puedo entender:

1. Supongamos que tenemos un algoritmo que se ejecuta en $1000n$ pasos. Por qué la gente dice que $1000$ deja de ser significativo cuando $n$ se hace muy grande (y por eso podemos tirarlo)? Esto realmente me confunde porque no importa lo grande que sea $n$ no es más que $1000n$ va a ser $1000$ veces mayor que $n$ . Y esto es muy significativo (en mi cabeza). Algún ejemplo de por qué se considera insignificante como $n$ tiende al infinito sería de agradecer.

2. ¿Por qué se dice a Big O que calcule el tiempo de ejecución en el peor de los casos? Dado el tiempo de ejecución $O(n)$ ¿cómo se considera el peor de los casos? Quiero decir que en este caso pensamos que nuestro algoritmo no es más lento que $n$ ¿verdad? Pero en realidad el tiempo de ejecución real podría ser $1000n$ y es efectivamente más lento que $n$ .

3. Según la definición, Big O nos da un límite superior escalado de $f$ como $n \to +\infty$ donde $f$ es nuestra función del tiempo. Pero, ¿cómo la interpretamos? Es decir, dado algoritmo que se ejecuta en $O(n)$ nunca podremos calcular el número real de pasos que da este algoritmo. Sólo sabemos que si duplicamos el tamaño de la entrada, duplicaremos también el tiempo de cálculo, ¿verdad? Pero si eso $O(n)$ algoritmo realmente toma $1000n$ pasos, entonces también tenemos que multiplicar el tamaño de la entrada por $1000$ para poder visualizar cómo crece, porque $1000n$ y $n$ tienen pendientes muy diferentes. Por tanto, en este caso, si duplicamos el tiempo de cálculo para el doble de tamaño de la entrada, nos haremos una idea equivocada de cómo crece el tiempo de ejecución, ¿no? Entonces, ¿cómo visualizar su tasa de crecimiento?

Quiero añadir que conozco la definición de Big O y cómo calcularlo, por lo que no es necesario explicarlo. Además ya he buscado en google todas estas preguntas montones de veces y no he tenido suerte. Estoy aprendiendo cálculo en este momento, así que espero haber hecho esta pregunta en el lugar correcto. Gracias de antemano.

Answer 1

La definición formal de la notación big-Oh consiste únicamente en definir un límite superior asintótico de la complejidad temporal que se mantiene para todas las entradas por encima de un determinado tamaño. Normalmente, nos referimos a la complejidad temporal en el peor de los casos, aunque podemos describir otras funciones del tamaño de la entrada de esta forma (como encontrar el orden de la complejidad temporal en el mejor de los casos o en el caso medio como función del tamaño de la entrada, cuánta memoria utiliza el programa, etc.). No siempre es eso lo que importa. A menudo, intentamos optimizar para obtener el mejor rendimiento medio en función del tipo de datos que esperamos obtener, pero el orden teórico de la complejidad temporal está dominado por algún caso límite que rara vez se da, o la función con mejor rendimiento asintótico sólo se alcanza en tamaños de entrada demasiado grandes para ser relevantes.

En un caso extremo, un algoritmo que siempre tardara exactamente un millón quinientos noventa y tres años y diez días en encontrar la respuesta tendría una complejidad temporal de ϴ(1). Por lo tanto, sería más rápido que uno que tardara ϴ(log log log N) para una entrada lo suficientemente grande, pero podría ser mucho más práctico utilizar el algoritmo que funciona más rápido en meros gigabytes o exabytes de datos.

Otro ejemplo muy conocido en el mundo real son los algoritmos de clasificación. Quicksort tiene una complejidad temporal de O(N²) en el peor de los casos, mientras que hay otros algoritmos de ordenación, como Mergesort, con una complejidad temporal de O(N log N). En el mundo real, sin embargo, muchos programas prefieren Quicksort a pesar de su peor complejidad temporal teórica. Esto se debe a que el mayor orden de complejidad temporal de Quicksort sólo significa que hay algunos caso, para datos superiores a algunos tamaño, donde Mergesort lo superaría. Pero, a menudo, no esperamos tener que lidiar nunca con esos casos inusuales, por lo que utilizamos el algoritmo que esperamos que sea más rápido la mayor parte del tiempo.

Por otra parte, si el límite superior de la complejidad temporal o de memoria no es el peor de los casos, puede que no le ofrezca la garantía de rendimiento en tiempo real o de uso de memoria que necesita. Si el sistema funciona muy despacio con entradas despreciables que "casi nunca" se producen, un atacante podría alimentarlo con entradas despreciables para denegar el servicio.

También recuerdo a Linus Torvalds hablando de parches que rechazó para el núcleo Linux a pesar de que tenían una complejidad temporal O(1) "óptima". Esto garantiza que, para algunos entradas de tamaño suficientemente grande, el algoritmo O(1) sería el mejor. Pero, a menudo, eso sólo era cierto para un caso muy raro o una entrada irrealmente grande, y Torvalds pensó que era más importante rendir bien en los casos más comunes.

Answer 2

El gran-Oh en una expresión como $f(x) = O(g(x))$ no dice nada sobre la magnitud de $f$ sobre un determinado dominio, sino que te dice cómo rápido $f$ aumenta/disminuye.

Por eso, por ejemplo, utilizar la notación big-Oh al cuantificar el error en una aproximación no tiene ningún sentido porque no te dice nada sobre la magnitud del error, sino que te dice a qué velocidad está disminuyendo/aumentando el error cuando la variable se acerca a un determinado valor.

Answer 3

Desde un punto de vista práctico, el número de pasos no es importante. La notación Big O nos da una idea de cuánto más tiempo o espacio ocupará nuestro algoritmo si aumentamos nuestra entrada.

• $O(n)$ nos dice que cuando duplicamos el tamaño de la entrada, duplicamos el tiempo necesario para resolver el problema. Si triplicamos el tamaño de la entrada, tardaremos el triple, etc. Los problemas $O(n)$ normalmente implican iterar a través de alguna colección un número fijo de veces.

• $O(n^2)$ nos dice matemáticamente que el tiempo necesario para procesar una entrada de $n$ elementos nos lleva unos $n^2$ cálculos. Intuitivamente, esto suele significar que tenemos un problema que requiere que iteremos a través de una colección una vez por cada elemento de la colección. Esto está bien para problemas pequeños, pero puede acarrear problemas para entradas grandes. Considere que un tamaño de entrada de mil millones tomaría alrededor de un segundo si la complejidad fuera $O(n)$ y unos treinta años para $O(n^2)$ . Si esto no parece probable, busca el problema de la percolación.

• $O(2^n)$ Estos problemas son intratables porque si añades un elemento a tu entrada duplicas tu tiempo.

• $O(\lg{n})$ es genial. Observe que utilizo $lg$ que es $\log_2$ . Esto significa un tamaño de entrada de mil millones (~ $2^{30}$ ) sólo tarda unos treinta cálculos en completarse. Podemos duplicar nuestra entrada y sólo necesitaremos un paso más para hallar el resultado. Vemos esto en una búsqueda binaria. Si añades una copia entera de tu árbol a una raíz común sólo necesitas una comparación más para hacer tu búsqueda.

Estos ejemplos deberían darte una idea de por qué utilizamos la notación. Normalmente no nos preocupa el tiempo de reloj exacto ni el uso de memoria. Queremos hacernos una idea de lo apropiado que es un algoritmo para un problema.

Answer 4

Grande- $O$ es un grueso medida de pedir de crecimiento. Su utilidad está en ignorando detalles. Del mismo modo, la media de una distribución ignora un gran número de detalles de la misma, pero sigue proporcionando información útil. Gran parte del progreso se basa en tomar algo complejo y separar lo que es importante (o real) de lo que son detalles quisquillosos (o ruido).

Uno podría preguntarse: "¿Cómo es un factor de 1000 'detalle (o ruido) quisquilloso'?". En ordenadores más lentos vagamente recientes tienen velocidades de reloj de unos pocos kHz. Los más rápidos, unos pocos GHz. Así que un factor inferior a un millón es una cuestión de ingeniería, no de selección de algoritmos. El principal uso de Big- $O$ está en la selección del algoritmo.

Si desea comparar dos tasas de crecimiento, en su GIF deberá escalar un que sean de altura $1$ -- "este orden de crecimiento es mi referencia con la que se compararán todos los demás órdenes de crecimiento". En tu GIF, si escalas $n^2$ para que sea su referencia, entonces verá $1000n$ y $n$ decayendo hacia $0$ como $1/n$ (este uso de "como" es "orden de crecimiento/disminución" y es bastante común utilizarlo así). Tanto $n$ y $1000n$ son finalmente insignificantes en comparación con $n^2$ y ambos son insignificantes en el mismo orden de crecimiento. Ampliando el GIF, para incluir $1000n^2$ se escala a la altura $1000$ que, aunque es mayor que $1$ ni crece ni se encoge $1000n^2$ tiene el mismo orden de crecimiento que $n^2$ . Si tiras $n^3$ en este gráfico crece de orden $n$ cuando se escala por $n^2$ . Por supuesto, también $2n^3$ y $1000n^3$ .

Una forma de ver que Big- $O$ es una medida gruesa es ver lo que se necesita para aterrizar fuera de $O(n)$ . Obsérvese que para cada $\epsilon > 0$ existe un $N_\varepsilon$ tal que para todo $n > N_\varepsilon$ , $1000n < n^{1+\varepsilon}$ . Así que cualquier elección de potencia mayor que $1$ acaba dominando $1000n$ . Por tanto, si agrupamos las tasas de crecimiento por potencias de $n$ , $1000n$ tierras en el " $n$ ". Pero Big- $O$ no sólo agrupa por potencias de $n$ una simple escalera de funciones distinguidas por Big- $O$ son exponenciales iterados. Big- $O$ distingue entre $n$ , $\mathrm{e}^n$ , $\mathrm{e}^{\mathrm{e}^n}$ etc. (Para un ejemplo de complejidad doblemente exponencial, véase "Algoritmo de Buchberger"). Big- $O$ distingue los poderes de $n$ . Grande- $O$ distingue los logaritmos iterados. En resumen, Big- $O$ distingue gran diferencias en el orden de crecimiento e ignora pequeño diferencias. El límite entre "grande" y "pequeño" está implícito en la definición de Big-. $O$ . Si, en una aplicación concreta, es preferible un punto de corte diferente, entonces utilice una medida de orden de crecimiento diferente.

El segundo problema es la medición del tiempo de ejecución en el peor de los casos. Pregunta: ¿Cuál es el tiempo de ejecución del algoritmo de detección de primos: "Prueba a dividir por 2, luego por 3, luego por 4, ... hasta la raíz cuadrada del número dado"? Varía. Para la mitad de los números enteros, este algoritmo se detiene después de una división. Para un tercio del resto, se detiene después de dos divisiones. Para una quinta parte del resto, se detiene después de tres divisiones. En el peor de los casos (es decir, cuando la entrada es realmente primo), el algoritmo realiza el peor número de divisiones. Si su resumen del algoritmo debe advertir cuando el tiempo de ejecución puede ser largo, entonces su resumen necesita informar del peor caso de tiempo. Tenga en cuenta que en esta configuración, también podemos informar del tiempo medio (aunque este cálculo es difícil). En general, para determinadas entradas, un algoritmo puede ser mucho más rápido que en el peor de los casos. Pero siempre, no es peor que su tiempo en el peor de los casos, así que si puede presupuestar ese tiempo en su calendario, puede estar seguro de obtener una respuesta antes de que sea necesaria. (Comentarios similares se aplican a la complejidad espacial. Si puede asignar el espacio del peor caso a su cálculo, puede estar seguro de que se completará sin abortar por falta de espacio).

Tu tercer punto no se sitúa en el contexto en el que se plantean realmente estas preguntas. Normalmente, uno implementa un algoritmo. Se conoce el orden de crecimiento de su complejidad en el peor de los casos. Sin embargo, los requisitos reales de tiempo y espacio del algoritmo son más matizados que el orden de crecimiento. Una implementación concreta puede tener una complejidad temporal $10^{-3}n^2 + 53 n + 10^5$ (corresponde vagamente a "hacer realmente el trabajo") ${} + {}$ "leer la entrada, escanear a través de tablas de búsqueda, y escribir la salida" ${} + {}$ "inicialización y otras tareas domésticas"). Cuando $n$ es pequeño, está dominado por los gastos fijos. Cuando $n$ es medio, éste está dominado por las actividades lineales. Una vez $n$ es lo suficientemente grande, sólo importa el término cuadrático principal. Sospecho que has estado pensando en estimaciones monomiales de la complejidad, por lo que no has pensado en la transición en el mundo real entre los órdenes de crecimiento de las distintas partes de una implementación. Fíjate en que los términos no principales son algo que podemos reducir variando la implementación: quizá podamos hacer una instantánea del contexto inicializado y cargarlo, reduciendo las contribuciones lineales y constantes a la complejidad. El término de orden principal, sin embargo, es algo con lo que estamos atascados. Podemos variar su coeficiente eligiendo hardware diferente, quizás hasta por un factor de un millón. Sin embargo, las dos preguntas a las que todo el mundo quiere respuesta son "¿cuánto tiempo tardaremos en responder a las preguntas que pretendemos hacer?" y "¿cuánto peor será si tenemos que hacer preguntas un poco más difíciles?".

El problema es que lo único que se suele saber es "el algoritmo que se ha aplicado es $O(n \log_2 n)$ ". Así que ejecute el algoritmo en pequeñas instancias de problemas de prueba para tratar de determinar dónde se produce el cambio de dominado por términos de orden inferior a dominado por el término principal y, a continuación, un pequeño número de problemas de prueba más grandes para garantizar que la tasa observada de crecimiento es la misma que la tasa teórica de crecimiento. Obsérvese que en ningún momento sirve de nada conocer el coeficiente teórico del término de orden principal, ya que primero ha sido anegado por los términos de orden inferior y luego por los diversos factores de escala implícitos inherentes a la aplicación. Una vez que conozca la tasa de crecimiento empírica de su implementación (y suponiendo que conozca la complejidad de entrada prevista), podrá empezar a responder a las dos preguntas.

Answer 5

Quizá pueda ayudar a comprenderlo. Cuando usted está buscando en los algoritmos que se ejecutan en la memoria, es bastante sencillo decir $100n$ es más rápido que $1000n$ . Sin embargo, las aplicaciones modernas suelen funcionar a través de redes. Esto puede cambiar su eficiencia de tiempo a $100ln$ vs $1000ln$ donde $l$ es la latencia. Las pruebas suelen realizarse en una red local, donde la latencia es muy pequeña.

Ahora, ¿qué pasa cuando tienes un proceso diferente donde la eficiencia del tiempo es $1000ln^2$ ? Si optimiza su código para reducir $1000$ a $100$ eso está bien, pero si un cliente cambia $n$ de $100$ a $1000$ Basándonos en sus datos, tu mejora de la eficiencia se ve empequeñecida por el cambio de sus datos. Esto es exactamente lo que ocurrió con uno de mis clientes. Teníamos un proceso que $O\left(n^2\right)$ pero no me di cuenta. $n$ superaba con frecuencia el millón, pero el tiempo de tramitación era aceptable (de un día para otro) cuando se encontraba en el mismo estado. Entonces, un cliente iniciaba el mismo proceso desde Estados Unidos al Reino Unido, lo que disparaba la latencia. Peor aún, la eficiencia real era algo así como $1000(ln)^2+50$ como $n$ representaba un dato a transferir. Jugueteando con el $1000$ o el $50$ NO iba a arreglar nada. Cambiarlo a $1000(ln)+100$ hizo. Pasando de $O\left(n^2\right)$ a $O(n)$ significaba que el aumento constante de los datos no provocaba un crecimiento explosivo del tiempo de procesamiento.

También he visto que esto ocurre en consultas SQL mal diseñadas. Ejecutar una consulta $O\left(n^2\right)$ y un $O(n)$ consulta a una base de datos con $100$ o $200$ discos, apenas se nota la diferencia. Cuando se despliegan esas mismas consultas contra una base de datos con $10,000,000$ registros o más, pasa de ser una consulta que tarda una hora en procesarse a una consulta que puede tardar una semana en procesarse, y empeora a medida que aumenta el número de registros.

Como referencia, puedes desenterrar un libro de pre-cálculo y encontrar la sección sobre familias de funciones. La idea básica de la notación Big-O es que, cuando se aleja lo suficiente, una familia de funciones parecen todas iguales, aparte de un factor de escala. Cualquier algoritmo que dependa de la entrada de datos del usuario o de factores del mundo real es probable que viole sus pruebas sencillas y se comporte de forma muy diferente a lo que sus cálculos afirman que "debería". Cambiar el Big-O de tu función a menudo hará mucho más para protegerte contra eso que cualquier ajuste en las constantes.