¿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

Big-O no pretende decirte exactamente cuánto tardaría en ejecutarse un algoritmo. Sirve para comparar algoritmos y para darte algunas ideas. idea general de tiempo de ejecución que:

• es independiente de la diferencia de tiempo de ejecución entre, por ejemplo, una comparación y una asignación
• no le importa si se ejecuta en una tostadora o en un clúster de superordenadores.
• no le importa cómo el factor constante puede cambiar para diferentes tamaños de entrada
• es una representación bastante simple y limpia (el tiempo de ejecución exacto de un $O(n^2)$ definido, por ejemplo, por el número de comparaciones, podría ser algo así como $20n^2 + 304n + 2587$ (que no suena tan bien).
• suele ser fácil de calcular

La mayoría de esas cosas no serían ciertas si tratas de inventar algo que te diga exactamente cuántos segundos tarda en ejecutarse algún algoritmo.

En la práctica, los factores constantes no suelen ser tan grandes.

Por lo tanto, aunque técnicamente esto no sea necesariamente cierto para cualquier tamaño de entrada del mundo real, puede estar bastante seguro de que $O(n)$ será más rápido que $O(n^2)$ para un tamaño de entrada grande. Por lo general, tiene sentido elegir el algoritmo con el menor big-O una vez que el tamaño de la entrada supera unos pocos cientos o miles de elementos (aunque también puede haber otras consideraciones que afecten a la decisión, como la facilidad de implementación), y evitar casi siempre los algoritmos de tiempo exponencial si el tamaño de la entrada es superior a 10-20 elementos.

Tampoco suele ser demasiado irrazonable hacer afirmaciones como estas: (aunque yo las tomaría con un grano de sal, y tendría en cuenta que pueden llegar a ser tremendamente inexactas dentro de unos años)

En un ordenador moderno medio, si tiene un tamaño de entrada de $10000$ elementos:

• $O(n)$ tardaría del orden de milisegundos.
• $O(n^2)$ tardaría del orden de segundos.
• $O(n^3)$ tardaría del orden de minutos.
• $O(n!)$ nos sobreviviría a todos.

Si utilizas un superordenador, probablemente puedas dividir el tiempo de ejecución por 100, si no más. Si utilizas una tostadora, es posible que tengas que multiplicarlo por 100. Pero es probable que no puedas pasar de tardar unos siglos a tardar unos milisegundos simplemente utilizando un ordenador diferente.

Utilizando directrices como las anteriores, uno debería ser capaz de hacerse una idea de si algún algoritmo va a terminar dentro de un tiempo máximo de ejecución para un tamaño de entrada dado en producción mucho antes incluso de escribir la primera línea de código.

Otra cosa que señalas que es útil:

Sólo sabemos que si duplicamos el tamaño de la entrada, duplicamos también el tiempo de cálculo.

Esto también es sólo una orientación aproximada. Un $O(n)$ puede tomar, por ejemplo $50n$ pasos cuando $n = 100$ pero $1000n$ pasos cuando $n > 100$ . Pero es una buena regla general.

Si ejecutas el algoritmo para 100 elementos, puedes calcular el tiempo que tardará para 1000000 elementos. Esto significa que puedes ejecutar un algoritmo para una pequeña muestra que tarda unos milisegundos para calcular si vas a tener que esperar minutos, días o siglos a que el algoritmo termine si lo ejecutas con tu entrada real.

En la práctica, rara vez nos preocupamos por visualizar la tasa de crecimiento. Lo razonamos a un nivel más teórico.

Nota: big-O es un límite superior, no el peor de los casos y $O(n)$ dice que el límite superior es $cn$ (para alguna constante $c$ ), no $n$ . Así que sigue siendo totalmente cierto para un algoritmo que toma $1000n$ .

Answer 2

Tantas respuestas pero no veo theta mencionado en ninguna parte, así que voy a tocar en eso.

¿Por qué se pide 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 que es el peor caso de comportamiento? 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 de hecho más lento que n.

Como otros han tocado, $O(n)$ es una familia. Dice - si la entrada es k veces mayor, el tiempo de ejecución es [como máximo] $k$ veces mayor. Y $O(n^2)$ es otra familia en la que $k$ veces mayor produce [como máximo] $k^2$ más tiempo.

¿Te has fijado en los corchetes? El caso es que $f \in O(g)$ no significa que $f$ crece de forma similar a $g$ . Significa que no crece más rápido. Por ejemplo, $x \in O(x^3)$ y $x^2 \in O(x^3)$ . Sólo limita su función desde arriba, nada más.

Si quieres una estimación más precisa, se llama Big Theta. El conjunto $\Theta(g)$ contiene todas las funciones que están acotadas por encima de y abajo por $g$ . Ej. $f \in \Theta(n^2)$ significa que para $k$ veces mayor de entrada $f$ es (al menos y como máximo) $k^2$ veces mayor.

También está el Gran Omega, que viene de abajo, es decir, significa "al menos así de despacio". Véase https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations

Answer 3

Voy a responder desde una perspectiva más CS-y, sino también incluir un poco numericy poco al final.

1. Hay dos puntos aquí. El primero es porque este factor se vuelve insignificante en contraste con $n$ si n crece lo suficiente. Una vez que usted está tratando con $n=10^{{10^{10}}^{10}}$ es que no hace una diferencia real si hay otro factor de 1000. Y la segunda es que solemos utilizar el big-O para diferenciar entre distintas clases; quizá sea útil pensar en ello a través de una medida aproximada: digamos que tenemos dos reglas, una mide un nanómetro y la otra 1000 veces más, es decir, un micrómetro. Si quisiéramos medir un campo de fútbol con estas reglas, este factor de 1.000 seguiría existiendo, pero en comparación con un telémetro láser que nos indicara inmediatamente la distancia, ambas serían inútiles.
2. Esto también está relacionado con la forma en que lo utilizamos. El factor no supone una diferencia real para valores suficientemente grandes de $n$ (tenga en cuenta que cuando se comparan algoritmos para un uso práctico real a menudo es no suficiente para comparar sus "clases de crecimiento" con big-O, pero en realidad habría que considerar los factores y los valores de $n$ que cabría esperar) y si lo comparamos con otro algoritmo de una categoría totalmente distinta, aún más. Así, si comparamos una función de $O(1000n)$ con otra en $O(x^2)$ sólo decimos que el $O(x^2)$ crece mucho más rápido que el $1000$ por adelantado no supone una diferencia real. Por eso solemos utilizar la palabra big-O para referirnos a funciones que, por así decirlo, pertenecen a ligas completamente distintas.
3. Esto es básicamente lo mismo otra vez. Sí, las líneas $f(n) = n$ y $g(n)=1000n$ tienen pendientes diferentes pero constantes en ambos casos. Si en lugar de eso se tomara $h(n) = n^2$ entonces a sólo $n=500$ el crecimiento de $h$ sería tan malo como $g$ pero sólo continuar empeorar a medida que $n$ creció. Supongamos que dibujas estas pendientes en un gráfico y empiezas a alejarlas. Las líneas de las funciones lineales $f$ y $g$ se acercarían cada vez más, pero se diferenciarían cada vez más de $h$ .

Así que, en general, tienes razón en que la notación big-O no es realmente útil cuando se comparan funciones dentro de una clase. Pero no es ahí donde la usamos; la usamos para comparar entre diferentes . Digamos que escribo una expansión taylor $\sin(x) = x + O(x^3)$ entonces realmente no me importaría si hubiera un $1000$ delante de eso $x^3$ - si conecto $10^{-9}$ para $x$ Obtengo básicamente $0$ en cualquier caso, que es probablemente todo lo que realmente me interesa. Si la expansión fuera $x + O(x)$ esto sería malo porque entonces $x$ y este término que quiero descuidar puede estar en el mismo orden de magnitud así que quizás en este punto empezaría a interesarme por el factor.

Answer 4

Sólo voy a abordar brevemente el punto nº 2 (y dejaré que otros aborden los puntos nº 1 y nº 3).

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? I 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$ .

Lo has entendido al revés. El Big-O no describe intrínsecamente el peor de los casos, sino que puede o no describirlo. La decisión de medir el comportamiento en el peor de los casos, en el mejor de los casos o en el caso medio se toma por adelantado; Big-O es entonces la métrica utilizada para medir cualquiera de esas dimensiones.

Por ejemplo Ordenación rápida algoritmo. Según Wikipedia:

• En el peor de los casos: $O(n^2)$
• En el mejor de los casos: $O(n \log n)$
• Rendimiento medio: $O(n \log n)$

Así que ya ves que hay diferentes valores de Big-O para los diferentes parámetros que se miden.

Answer 5

Matemáticamente hablando, el gran $O$ describe un pedido previo $~\preceq$ (que es como una ordenación parcial sin requisito de antisimetría) sobre secuencias infinitas de (normalmente positivos, lo que de hecho supondré en la discusión a continuación) números reales, que depende sólo del comportamiento asintótico de las secuencias. La relación $f\preceq g$ se escribe $f(n)=O(g(n))$ y expresa el hecho de que $f(n)$ no crece mucho más rápido que $g(n)$ para un $n$ . Es tal que la relación de equivalencia correspondiente (que se mantiene entre secuencias $f$ y $g$ cuando ambos $f\preceq g$ y $g\preceq f$ y se escribe $f(n)=\Theta(g(n))$ ) es bastante tosco, y esto es intencionado. Así, se puede sustituir, a efectos de comparación por $~\preceq$ una secuencia por cualquier otra de su clase de equivalencia, y esto permite simplificar las expresiones para $f(n)$ eliminando términos insignificantes.

Para ello, se podrían definir diferentes pedidos previos. El requisito mínimo es que $f\preceq g$ siempre que exista $N\in\Bbb N$ tal que $f(n)\leq g(n)$ para todos $n\geq N$ (Abreviaré esto como $f(n)\leq g(n)$ como $n\to\infty$ ). Pero si se toma eso como los únicos casos en los que $f\preceq g$ es válida, entonces la clase de equivalencia de $f$ es extremadamente pequeño: consiste en el $g$ para lo cual $f(n)=g(n)$ como $n\to\infty$ es decir, que difieren de $f$ sólo en un número finito de lugares. Incluso añadiendo un término de crecimiento muy lento como $\log\log\log n$ a una secuencia de rápido crecimiento como $n!$ daría una secuencia no equivalente. Es razonable querer ignorar (en el sentido de permanecer en la misma clase de equivalencia) las contribuciones añadidas a $f$ que crecen lentamente en relación con $f$ sí mismo. Esto puede lograrse comparando con un múltiplo escalar de $g$ . En términos del conjunto (cerrado hacia arriba) de $C>1$ para lo cual $f(n)\leq Cg(n)$ como $n\to\infty$ hay dos opciones válidas para definir " $\preceq$ "(1) definir $f\preceq g$ siempre que este conjunto sea todo $\Bbb R_{>1}$ (equivalentemente: su mínimo es igual a $1$ ), o (2) definir $f\preceq g$ siempre que este conjunto no sea vacío. Ninguna otra opción conduce a una relación transitiva " $\preceq$ ", por ejemplo exigiendo $C=2$ para estar en el conjunto no lo consigue porque entonces $(3n)_n\preceq(2n)_n\preceq(n)_n$ pero $(3n)_n\not\preceq(n)_n$ . Como nota al margen, observe que $f=o(g)$ significa que el conjunto de todos los $C>0$ con la misma propiedad es todo $\Bbb R_{>0}$ .

Ambas opciones (1) y (2) hacen que $f$ equivalente a $f+g$ siempre que $g=o(f)$ lo que permite ignorar los "términos despreciables" en la expresión de una sucesión. Aun así (1) da una equivalencia considerablemente más fina que (2), ya que no hay dos múltiplos escalares de la misma secuencia que sean equivalentes. Puede que te sientas inclinado a pensar que eso es bueno, ya que (como sugiere tu pregunta) intuitivamente la secuencia $f$ corresponde a una eficiencia mucho mayor que $1000f$ (aunque no le servirá de mucho cuando $f(n)=n!$ aunque importaría para $f(n)=n$ o incluso más en caso $f(n)=\log(n)$ ). Pero se vería obligado a considerar también $f$ ser estrictamente mejor que $1.00007f$ donde la diferencia parece ser menor. La razón principal por la que la gente prefiere la opción (2), que da la definición real de $O(f)$ es que la opción (1) obliga a tener en cuenta detalles minúsculos difíciles de estimar. Por ejemplo, si una tarea se realiza mediante un simple bucle iterado $n$ cuando el tiempo de una sola iteración es constante o puede acotarse de forma que no dependa de los detalles de la iteración, podemos decir que la tarea se completa en $O(n)$ tiempo con la definición (2). Sin embargo, con la definición (1), en primer lugar habría que introducir una unidad de tiempo, como un ciclo de reloj, y, en segundo lugar, calcular el número exacto de estas unidades para el cuerpo del bucle. Pero eso depende de detalles como la secuencia exacta de instrucciones que produce el compilador, y es algo de lo que la mayoría de la gente no quiere preocuparse. Dicho esto, se puede intentar clasificar primero los métodos en el sentido habitual de $O(f)$ , y luego entre los métodos que son equivalentes para este método intentar distinguir los más y menos eficientes basándose en el factor constante que aparece al comparar dos de ellos. Knuth lo hace en muchos casos (al igual que la gente que intenta promover el quicksort, ya que es la única manera de hacer que ese algoritmo brille en comparación con alternativas como el heapsort), pero esto requiere para una comparación algo justa cosas como contar pasos después de convertir a código máquina para alguna máquina idealizada.

Así que para responder a las preguntas concretas. 1. aunque considerando el factor constante entre secuencias que son equivalentes en la gran $O$ sentido pueden ser relevantes, sería a la vez demasiado engorroso tener que preocuparse de los cambios en dichos factores a la hora de determinar la clase de eficiencia de un algoritmo, y casi imposible determinar las constantes precisas de forma neural y objetiva. 2. La gran $O$ compara secuencias, y no le importa lo más mínimo lo que estas secuencias miden. Si son secuencias de eficiencias en el peor de los casos, eso es lo que expresará la notación, pero también podrían ser eficiencias medias (o incluso en el mejor de los casos). 3. Al tratarse de una medida asintótica, no hay grandes $O$ estimación dice nada en absoluto sobre ningún valor concreto $f(n)$ : si cambias ese valor arbitrariamente, o finitamente muchos de ellos, esto no cambia nada sobre el gran- $O$ estimación. Así que ya es vano esperar que se extraigan conclusiones sólidas sobre el tiempo de ejecución aislado a partir de big- $O$ estimaciones. El hecho de que además no se lleve ninguna información sobre un factor constante no lo hace fundamentalmente peor; esto simplemente no es lo que el gran $O$ cálculo está destinado. Si quieres comparar tiempos de ejecución concretos, olvídate de big- $O$ y ejecutar pruebas comparativas. Uno de los aspectos en el arte de la programación es saber cuándo hay que preocuparse por los grandes $O$ hechos, y cuándo no.