¿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

¿Qué te dice realmente Big O? Edita: responder a esta pregunta en el contexto de la complejidad computacional, y no en general.

Te dice que si un algoritmo es $O(f(n))$ entonces, en principio, se puede construir una máquina física tal que el algoritmo se ejecute exactamente en $f(n)$ pasos, o en el caso de que $f(n) = n$ arbitrariamente cerca de $n$ pasos.

Respuesta a la primera pregunta

No he visto a nadie mencionar el punto principal aquí. Todas las demás respuestas son correctas, es decir, la complejidad asintótica no es una herramienta de evaluación comparativa. Sin embargo, esto no responde a la pregunta de qué es la complejidad asintótica realmente útiles en el contexto de la teoría de la complejidad.

Hay que entender el contexto original en el que se inventó esta sintaxis en relación con los algoritmos. La idea es que esto describe el rendimiento de, no software, pero máquinas . Por ejemplo, las máquinas de Turing. La máquina de Turing fue un concepto inventado precisamente para tener una abstracción de las máquinas de computación en general.

¿Qué tiene esto que ver con la complejidad asintótica? Bueno, digamos que ejecutas tu $O(n)$ algoritmo en una máquina de Turing y se ejecuta en exactamente $1000n$ para cualquier cadena de entrada de tamaño $n$ . Existe un teorema que dice que se puede "construir" una máquina de Turing diferente tal que el algoritmo tarde casi exactamente $n$ pasos a seguir.

En otras palabras, aunque es cierto que el cualquier máquina en particular es posible que un $O(n)$ algoritmo sea en la práctica más lento que un $O(n^2)$ algoritmo, lo que nos dice la teoría de autómatas es que siempre es posible construir una máquina tal que el $O(n)$ será en la práctica más rápido que el algoritmo $O(n^2)$ posiblemente a expensas del rendimiento de otros algoritmos.

Así que para responder a su primera pregunta

Por qué se dice que el coeficiente 1000 se vuelve insignificante cuando

Answer 2

1. Es significativo $1000$ en $1000n$ o no es posible decirlo si tenemos la misma comprensión del significado. De gran- $O$ punto de vista allí sostiene $$O(1000n) = O(n)$$ Por lo tanto, definen el mismo conjunto.

2. $O(n)$ no se define para la estimación sólo para el peor de los casos. ¿Dónde está escrito? A grandes rasgos, se trata de un conjunto de funciones que es mejor, luego se escala $n$ en la vecindad infinita.

3. La visualización depende de quien la crea y si tendrá una impresión equivocada ¿cómo podemos saberlo?

Suma con respuestas a https://i.stack.imgur.com/OGY8L.png del chat https://chat.stackexchange.com/rooms/129614/discussion-on-answer-by-zkutch-why-to-calculate-big-o-if-we-can-just-calculate

Para ser pedante sabiendo, que $g \in O(f)$ es no saber nada, porque bajo "nada" entiendo, que la información sobre $g$ es $\emptyset$ . $g \in O(f)$ es muy buena información en algunos casos, es mala información en otros, pero no es "nada".

Para basar las propiedades y la definición de big- $O$ en la concepción del límite no es muy buena idea, porque en muchos casos el límite de la relación $\frac{f}{g}$ no existe, sino que se mantiene $g \in O(f)$ . Una decisión es utilizar $\limsup$ pero no a una basada en el límite. Permítanme aquí decir más, que, personalmente no prefiero la definición basada en la proporción $\frac{f}{g}$ ya que esta forma no tiene sentido para $g$ que tienen una subsecuencia de ceros.

Dicho esto y pasando a tu segundo párrafo permíteme decir, que ese factor constante es insignificante en ambos casos: cuando comparamos funciones de un gran- $O$ o de diferentes. Grande- $O$ "come" constantes en ambos casos.

Tercer párrafo. ¿Por qué hay que subrayar la palabra "SÓLO"? Puede que alguien use, o vaya a usar, grandes $O$ con algún propósito, que aún no mencionan.

Cuarto párrafo. Tomemos algunas $O(F)$ . Si por "clase superior" se entiende tal $O(G)$ para lo cual $F\in O(G)$ entonces no podemos decir nada sobre $\lim\limits_{n\to\infty}\frac{g_1(n)}{f(n)}$ donde $g_1 \in O(G)$ y $f \in O(F)$ porque $O(F)\subset O(G)$ . Si tenemos $F \leqslant G$ y luego otra vez $O(F)\subset O(G)$ y de nuevo límite de la relación probablemente no existe o es cualquiera, si existe.

Escribe, por favor, aquí o en el chat, si algo no te queda suficientemente claro.

Answer 3

Un ejemplo que siempre me ha encantado está en esta página web:

http://www.batmath.it/matematica/a_taylor/pg8.htm

Está en italiano, pero no hay mucho que leer, lo reproduciré aquí. Para la función $$ g(x)=\begin{cases} 2e^{-1/4x^2}\int_0^{1/4x}e^{4t^2}\, dt, & x\ne 0 \\ 0, & x=0, \end{cases}$$ la aproximación de Taylor en realidad empeora a medida que aumenta el grado de la aproximante (véanse las imágenes de la página enlazada; hay que hacer clic en "uno, due, tre, quattro, cinque, sei, sette" para ver las aproximaciones sucesivas).

El motivo es que, aunque $$ g(x)=P_n(x) + O(x^{n+1}), \quad \text{as }x\to 0, $$ donde $P_n$ denota el $n$ -ésimo grado de Taylor, la constante implícita en el big-O depende de $n$ . Y para este ejemplo concreto, la constante crece muy rápido como $n$ aumenta. Por lo tanto, la aproximación es buena en una pequeña vecindad del origen, pero dicha vecindad en realidad encoge como $n$ aumenta, para compensar el crecimiento de la constante implícita.

En resumidas cuentas, tiene usted razón. La O grande significa lo que significa: una desigualdad con una constante implícita. Omitir esa constante puede ser psicológicamente genial, pero tiene sus trampas.

Answer 4

1. Big O es un concepto matemático que nos permite descartar información sistemáticamente. Según la definición, puedes demostrar que los factores constantes son "insignificantes" y no afectan al Big O de una función (ejercicio para ti). Esta prueba te dirá el significado de "insignificante" en este contexto: una heurística para calcular el Big O. Pero, ¿por qué no elegir otra definición de Big O? Buena pregunta.

2. De hecho, Big O no calcula el tiempo de ejecución en el peor de los casos. A veces es posible modelar la contribución de un algoritmo al tiempo de ejecución de un sistema físico mediante una función $f$ asignación de "tamaño de entrada" a número de "pasos". Hay mucha flexibilidad a la hora de elegir $f$ . Para un algoritmo de ordenación, se podría medir cuántas comparaciones de pares de elementos se requieren por término medio para una lista de longitud $n$ donde se supone que los elementos de la lista son independientes y están uniformemente distribuidos. Ahora podría intentar calcular $f$ exactamente, o podrías aplicar Big O. Entonces, como una forma abreviada, podrías decir que tu Big O estima un límite superior en el tiempo medio de ejecución del caso.

3. Tienes razón, Big O no te dice nada sobre tiempos de ejecución concretos. Para un $O(n)$ algoritmo de tiempo, duplicando $n$ no significa necesariamente duplicar el tiempo empleado. Siempre que te encuentres con una nueva definición matemática, es útil elaborar una lista de ejemplos. Dices que conoces la definición de Big O y sabes cómo calcularla, pero ¿tienes ejemplos? (Ten en cuenta que se puede abusar de la terminología, anota también esos ejemplos). $$ \begin{aligned} f(n) &= 1000 + n &\implies f \in O(n) \\ f(n) &= \frac{1000}{n} + \frac{n}{1000} &\implies f \in O(n) \\ f(n) &= \sqrt{n} &\implies f \in O(n) \\ f(n) &= 2^{1000n} &\,\,\,\,\not\!\!\!\!\implies f \in O(2^n) \end{aligned} $$

---

Vale, ¿por qué no otra definición de Big O? ¿Por qué descartar información? ¿Por qué no descartar aún más información?

En primer lugar, la función $f$ puede ser demasiado difícil de calcular con exactitud, incluso para el sencillo ejemplo de un algoritmo de ordenación.

En segundo lugar, a menudo $f$ ya es una medida imprecisa de la realidad y, por tanto, utilizar el Big O es una descripción más veraz. Una regla mide en milímetros, así que da tu medida en milímetros con un intervalo de confianza. Del mismo modo, si no sabes en qué máquina se ejecutará tu algoritmo, dale a tu algoritmo 'medida' con Big O y Gran Omega .

En tercer lugar, hay alternativas. Suave O descarta los factores logarítmicos. En la práctica, Big O encuentra el equilibrio adecuado en la mayoría de las situaciones. También hay formas de utilizar Big O en estimaciones cada vez más refinadas. Por ejemplo, $\ln(n!)$ es trivial en $O(n \ln n)$ pero Aproximación de Stirling da $\ln(n!) = n \ln n - n + O(\ln n)$ . Creo que este uso de la O grande es más común en el análisis real que en el diseño de algoritmos.

En cualquier caso, si ya dispone de descripciones exactas $f(n) = n$ y $g(n) = 1000n$ y no están modelando el mundo real, entonces Big O no es la herramienta para ti.

Answer 5

En ya se ha dicho Big O no mide la velocidad, sino la capacidad de escalado. Por eso es muy útil para comparar algoritmos de diferentes clases de escalado. Por ejemplo, para grandes conjuntos de datos, un algoritmo loglineal ( $\mathcal{O}(n\log n)$ ) (por ejemplo, quicksort) superará a una ordenación cuadrática ( $\mathcal{O}(n^2)$ ) (por ejemplo, ordenación por inserción). Por lo tanto, las personas que tienen que manejar grandes conjuntos de datos utilizan la ordenación rápida en lugar de la ordenación por inserción. Pero Big O no te dice si la ordenación por inserción es más rápida que la ordenación burbuja. Y sobre todo no te dice lo bien que manejará tus datos. La ordenación por burbujas puede ser excelente para ordenar datos casi ordenados. Hace la validación en tiempo lineal. La ordenación por inserción es más simple y rápida que la ordenación rápida para pequeñas cantidades de datos.

En la pregunta, usted dijo

Supongamos que tenemos un algoritmo que se ejecuta en $1000n$ pasos.

En realidad, es bastante difícil de calcular.

Considera que tengo una variable en mi programa que es accesible globalmente. Le doy un valor. Hago un montón de cosas, suficientes para que la variable sólo se almacene en RAM, no en caché ni en un registro. Quiero añadir uno a esa variable. ¿Cuántos pasos son?

Podrías señalar que existe literalmente una instrucción para añadir uno a una variable (supongamos que existe una para esa plataforma). Pero esa instrucción asume que la variable está en un registro. Así que necesitamos cargar la variable en un registro. Tenemos una instrucción para eso. Pero esa instrucción asume que la variable está en caché. Ignorando los diferentes niveles de caché (y la paginación a disco), necesitamos cargar la variable desde la RAM. Pero resulta que en realidad no tenemos una instrucción para cargar una sola variable de la RAM a la caché (y mucho menos a un registro). Lo que tenemos es la capacidad de cargar un bloque de RAM en la caché.

Vale, esto es más complicado de lo que parecía al principio. Pero seguimos jugando. Averiguamos qué bloque de memoria contiene la variable. Eso puede llevar algunos pasos propios, digamos cinco. Entonces emitimos la instrucción de carga. Ahora descubrimos que, como la RAM es más lenta que la caché, esta instrucción tarda varios pasos en terminar. Algo así como empezar a cargar, noventa y ocho pasos de espera, terminar de cargar. Si tenemos otro trabajo, podemos hacer eso en lugar de los noventa y ocho pasos de espera. Pero asumamos que no podemos hacer ningún otro trabajo hasta que tengamos esta variable incrementada.

Finalmente tenemos el valor de la variable cargado en caché. Ahora necesitamos emitir otro comando para cargarlo desde la caché a un registro. Así que lo hacemos. Resulta que eso lleva otros diez pasos de tiempo. Una vez en el registro, podemos incrementarlo. Hay 116 pasos para hacer una línea de código. Y esa era una línea de código realmente simple.

Una vez que tenemos el valor incrementado, podemos utilizarlo para lo que necesitábamos. Vamos a calcular otros diez pasos. Ahora, queremos incrementarlo de nuevo. ¿Necesitamos otros 116 pasos? No, ya está en el registro. Podemos hacer la misma instrucción en un solo paso. Así que hemos incrementado el valor dos veces en sólo 127 pasos. De los cuales 115 fueron sólo para llegar al punto de partida. Pero desde la perspectiva del código que escribimos, esa fue la misma instrucción de alto nivel. Entonces, ¿cómo convertimos el código de alto nivel en pasos?

No podemos limitarnos a contar líneas de código. Algunas líneas requerirán más trabajo que otras. Ni siquiera podemos estar seguros de cuántos pasos pueden llevar líneas de código idénticas. A veces un simple incremento puede tomar un paso. A veces 116. (Es realmente difícil contar el número de pasos en código compilado o interpretado. Tan difícil que rara vez lo intentamos. Es mucho más probable que utilicemos un perfilador o un benchmarking para medir el tiempo que tarda en ejecutarse un programa.

Pero a Big O no le importa. Sólo asume que el tiempo será relativamente consistente. De tal manera que duplicar el tamaño de los datos puede duplicar el tiempo que tarda en ejecutarse. O cuadruplicarlo. O aumentarlo un 40%. O triplicarlo. Por lo general, será más rápido utilizar la O grande más pequeña. Y para los casos en los que no lo sea, podemos recurrir a la creación de perfiles y a la evaluación comparativa. Pero ha sido muy raro que haya intentado contar el número de pasos, y nunca profesionalmente. Es el tipo de análisis que se suele hacer en el mundo académico con fines ilustrativos. En realidad, no funciona en la programación real. Porque los compiladores y las CPU son mucho más complicados que el simple procesamiento de pasos.

De hecho, son más complicados que este ejemplo. En concreto, la idea de "pasos de espera" entre los pasos de inicio y fin es algo cuestionable. Pero esa ilustración facilita la reflexión sobre lo que ocurre, aunque no sea una descripción precisa de lo que ocurre en realidad.

Big O ayuda principalmente a que los programadores eviten los verdaderos errores, como calcular la secuencia de Fibonacci recursivamente como un árbol binario. Tenemos una solución de tiempo lineal bastante sencilla, una solución de tiempo constante más complicada para un único valor de la secuencia y una solución recursiva elegante pero de tiempo exponencial. No se me ocurre ninguna circunstancia en la que queramos la solución de tiempo exponencial (aparte de demostrar que es lenta). Pero tanto la solución lineal como la de tiempo constante podrían ser óptimas para un caso de uso determinado.

Si realmente necesitas optimizar un programa, no puedes detenerte con Big O. Necesitas continuar con la creación de perfiles y la evaluación comparativa. Big O ayuda a evitar algunos grandes errores. Pero hay muchos errores que nunca detectará.