¿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

Leyendo entre líneas, creo que puede estar malinterpretando el análisis Big O como sustituto de la evaluación comparativa. No es así. Un ingeniero todavía tiene que evaluar su código si quieren saber cómo rápido lo es. Y, de hecho, en el mundo real, un $\mathcal{O}(n)$ puede ser más lento que un algoritmo $\mathcal{O}(n^2)$ en conjuntos de datos reales.

Pero como $n$ se acerca al infinito, el $\mathcal{O}(n^2)$ algoritmo será, en última instancia, más lento. Por poner un ejemplo, si permitimos factores constantes en nuestra notación Big-O, entonces un $\mathcal{O}(10n)$ algoritmo dará más "pasos" que un $\mathcal{O}(n^2)$ algoritmo, si $n$ es inferior a $10$ ( $10\cdot 10 = 10^2$ ).

Pero si $n$ es $100$ entonces el $\mathcal{O}(n^2)$ tarda diez veces más. Si $n$ es $1000$ tarda cien veces más. En $n$ crece, también lo hace esta diferencia. Que manera en que difieren ambos algoritmos es lo que estamos analizando cuando utilizamos el análisis Big O.

Esperemos que este ejemplo también aclare por qué el factor constante es irrelevante y puede ignorarse. Que sean diez, cien, mil, un millón o un cuatrillón en última instancia no importa, porque como $n$ se acerca al infinito, el $\mathcal{O}(n^2)$ al final va a ser más lento de todos modos. Ese es el poder del crecimiento exponencial.

El quid de la cuestión es que el análisis Big O es un concepto matemático que NO le dice a un ingeniero a qué velocidad va a funcionar algo o cuántos pasos va a dar. Para eso está la evaluación comparativa. El análisis Big O sigue siendo una herramienta muy útil en el diseño de algoritmos, pero si estás interesado en saber exactamente cuánto tiempo tarda algo en ejecutarse, tendrás que hacer pruebas con datos reales.

Gran resumen en los comentarios de @chepner:

Dicho de otro modo, Big O no se utiliza para comparar tiempos de ejecución, sino para comparar cómo se escalan esos tiempos de ejecución a medida que crece el tamaño de la entrada.

Answer 2

Los algoritmos no tienen "velocidad". La velocidad de ejecución de un algoritmo en la práctica depende de la forma en que se implemente y del hardware y software de apoyo en que se ejecute. Así que la velocidad de un algoritmo no depende sólo del algoritmo en sí y, por tanto, es extremadamente difícil de analizar matemáticamente. Para una entrada dada, el algoritmo A puede ejecutarse diez veces más rápido que el algoritmo B en un tipo de ordenador, pero sólo la mitad de rápido que B en otro tipo.

Así pues, la "velocidad" de un algoritmo es un concepto teórico mal definido: en prácticamente todas las circunstancias sólo puede determinarse experimentalmente. En cambio, la notación Big-O analiza una propiedad de los algoritmos relacionada con el rendimiento que puede expresarse matemáticamente: no su velocidad, sino su rendimiento. escalas . Es decir, Big-O no te dice cómo rápido un algoritmo es en términos absolutos, sino sólo cómo su "velocidad" cambia cuando se cambia el tamaño del problema (por ejemplo, el número de elementos a ordenar) . Por ejemplo, para un algoritmo O(n²), duplicar el tamaño del problema multiplicará por cuatro el tiempo de ejecución, mientras que duplicar el tamaño del problema para un algoritmo O(n) sólo duplicará el tiempo de ejecución.

Como herramienta que sólo debe responder a preguntas sobre la escalabilidad, pero no sobre el rendimiento absoluto, los factores constantes no importan, porque no cambian el comportamiento de la escalabilidad: Un algoritmo O(n²) cuadruplicará su tiempo de ejecución cuando se duplique el tamaño del problema, independientemente de cuál fuera el tiempo de ejecución original. Por ejemplo, para un conjunto de problemas de tamaño n=1000, un algoritmo O(n²) puede tardar un microsegundo, mientras que otro algoritmo O(n²) puede tardar dos horas. La notificación Big-O no se ocupa de estas diferencias absolutas. Sin embargo, sí le indica que ambos algoritmos cuadruplicarán aproximadamente su tiempo de ejecución cuando duplique el tamaño del conjunto de problemas a n=2000: el más rápido de estos dos algoritmos de ejemplo de un microsegundo a cuatro microsegundos, y el más lento de dos horas a ocho horas.

Teniendo en cuenta esta limitación, Big-O no es un sustitución para las mediciones de velocidad, pero es más fácil de obtener y lo suficientemente útil por sí mismo como para basar ciertas decisiones en él sin necesidad de mediciones experimentales.

Answer 3

Tienes razón: El $O$ la notación sólo te dice lo grande que es dentro de un factor constante. Si desea algo más preciso que eso, no utilice $O$ . La razón por la que $O$ notación es ampliamente conocida y utilizada es: se ha encontrado útil a lo largo de los años. Por supuesto, en algunos entornos, otras estimaciones pueden ser más útiles que $O$ .

Answer 4

Creo que todo esto ya se ha tratado antes (¡incluso en mse!), pero quizá no en una sola respuesta, así que diré a̶ ̶f̶e̶w̶ ̶w̶o̶r̶d̶s̶ (tanto para "unos pocos" :P) aquí.

En cuanto a (1), creo que no entiendes la importancia de "eliminar" los factores constantes y los términos de orden inferior. Cuando analizamos el tiempo de ejecución de un algoritmo, lo hacemos en algún modelo de cómo funcionan los ordenadores, y hay una gran variedad de opciones. Normalmente trabajamos con alguna versión del Modelo Word-RAM pero hay un puñado de opciones de bajo nivel que puedes elegir. La noción de cálculo es extremadamente robusto, pero la noción de tiempo de ejecución no lo es. Queremos saber que a nuestra noción de tiempo de ejecución no le importa qué modelo preciso utilicemos, porque diferentes modelos modelan diferentes facetas de los ordenadores del "mundo real". Dependiendo del modelo que utilices, las constantes precisas de tu tiempo de ejecución podrían cambiar por factores constantes, o podrían recoger términos de orden inferior. Esto es análogo a no poder decir exactamente cuántos pasos tardará en ejecutarse un cálculo, ya que eso depende del hardware preciso en el que se esté ejecutando, así como de los detalles específicos de cómo se implementa el algoritmo (más que del algoritmo en sí). Lo que puede decir, sin embargo, es que "hasta los términos de orden inferior", el tiempo de ejecución es coherente. Así que descartamos los términos de orden inferior, porque pueden verse influidos por el hardware o los detalles de implementación.

Sin embargo, todavía requiere cierta justificación saber que desechar factores constantes "no importa realmente", y este es por lo que la gente suele hablar de cómo $1000n$ "no es mucho más grande" que $n$ siempre que $n$ es extremadamente grande. Y quiero decir extremadamente . Si tomamos $n \approx 10^{10,000}$ entonces $1000n \approx 10^{10,003}$ . En este caso, la diferencia realmente es pequeño en comparación con el resto de los números implicados.

Además, a pesar de lo que te digan en las clases de introducción a la programación las constantes realmente importan . No podemos decir exactamente lo que son (por las razones que he mencionado anteriormente), pero se puede saber si sus constantes son $\approx 1000$ o si son $\approx 2$ y tienes toda la razón al pensar que son números diferentes.

En el mundo real, si tienes un algoritmo cuadrático con una constante pequeña y un algoritmo lineal con un enorme constante, a menudo es mejor utilizar el algoritmo cuadrático porque casi nunca ejecutar nuestro código en entradas de tamaño $10^{10,000}$ . De hecho, ya lo estamos haciendo: Hay un montón de algoritmos para los que nuestro big-O teórico es más pequeño que el algoritmo utilizado en la práctica, pero el algoritmo teórico nunca se utiliza porque las constantes implicadas son muy grandes. Estos algoritmos se denominan galáctico y quizá saber que existen te ayude a sentir que no te estás volviendo loco preocupándote por estas cosas.

---

Para (2), "el peor caso" se refiere a la peor de todas las entradas posibles. Por ejemplo, supongamos que queremos escribir un código que compruebe si una lista tiene un número par. Hay un algoritmo obvio para hacerlo

for x in list:
  if isEven(x): return True
return False

En la lista $[2,3,4,5,6]$ ¡este algoritmo funciona super rápido! Porque el primer elemento ya es par. En la lista $[1,3,5,7,9,11,13,14]$ se ejecuta con relativa lentitud, porque tiene que esperar a que el muy final para ver si existe o no un número par.

Esto sí no tienen que ver con $1000n$ siendo mayor que $n$ . Recuerde que lo que realmente es el tiempo de ejecución hasta las constantes, porque si utilizas un modelo de computación realmente malo, o si tienes muy mala suerte con el ordenador que utilizas, podrías obtener factores constantes adicionales en tu tiempo de ejecución sin cambiar realmente tu algoritmo en absoluto.

Esto contrasta con el tiempo de ejecución del "caso medio", por ejemplo. En este caso, en lugar de mirar el máximo de todos los tiempos de ejecución posibles, miramos el media de los posibles tiempos de ejecución. Como ejemplo en el que esto importa, se puede demostrar que ordenación rápida toma $\approx n^2$ muchos pasos en el peor de los casos, pero $\approx n \log n$ pasos de media.

---

Para (3), hay una diferencia sustancial entre, digamos, $n^2$ y $n \log n$ y $n$ . Saber cómo se escala el tiempo de ejecución a medida que se escala la entrada sigue siendo un factor importante a la hora de decidir qué algoritmo utilizar. Por ejemplo, para utilizar el tipo de números que te preocupan, supongamos que multiplicamos el tamaño de nuestra entrada por $10,000$ . ¿El tiempo de ejecución se multiplica por un factor de $100,000,000$ por un factor de $10,000$ (más un factor aditivo adicional de $40,000n$ ), o por un factor de $10,000$ ? Obviamente esto importa un lote y se puede ver que para entradas de tamaño $1,000,000$ (que es pequeño en comparación con algunos tamaños de entrada con los que trabajan empresas reales como google), un $n^2$ va a ser más lento que un algoritmo $1000n$ algoritmo.

---

Espero que esto ayude ^_^

Answer 5

La utilidad de la comparación es la siguiente: No importa que cambies los "parámetros", sigues llegando al mismo factor de crecimiento general. Sí, 1000n es 1000 veces mayor que n. Eso es obvio. ¿Pero qué pasa si actualizas tu cpu o lo ejecutas en dos hilos? ¿Qué pasa entonces? Bueno, INDEPENDIENTEMENTE, los algoritmos se seguirán comportando de la misma manera. n y 3n y 9n y 0,3432n todos se comportarán de la misma manera independientemente de que el proceso se ejecute" porque el proceso depende linealmente de n.

Lo que nos dice O(n) es precisamente cuánto tiempo necesita el algoritmo para engullir cada vez más datos.

Por ejemplo, supongamos que tenemos un algoritmo A que toma un conjunto de datos S y da como resultado T. Podemos representarlo como T = SA donde podemos usar notación polaca inversa para expresar cualquier complejo de algoritmos, por ejemplo 'T = SAB+RBAAA' donde puedes interpretar las operaciones como quieras (simplemente léelo de izquierda a derecha).

Entonces el rendimiento absoluto de los algoritmos podría cambiar con diferentes cpus, digamos, si todos están en la misma clase bajo equivalencia O(n) todos corren igual(bajo equivalencia, no igualdad absoluta).

Piénsalo con más delicadeza: Sea A_k el algoritmo en su "paso k". Otro algoritmo que procese exactamente los mismos datos sería el algoritmo en el paso B_k.

Entonces O(n) nos dice que A_{k+1}/A_k y B_{k+1}/B_k son ambos de la misma clase. O(n) es en realidad la clase de equivalencia para cualquier familia de funciones que crezcan todas a la misma tasa funcional.

Por ejemplo, supongamos que A_k tarda 20 segundos en pasar al estado A_{k+1} y 15 segundos en pasar del estado A_{k+1} a A_{k+2}. Supongamos que tenemos un ordenador más rápido que ejecuta A, al que llamaremos B. Ahora B_k tarda 15 segundos en ir al estado B_{k+1} y 11,3184 segundos en ir del estado B_{k+1} a B_{k+2}.

Entonces 15/20 = 0,75 = 11,3184/15.

Es decir, ambas máquinas requieren la misma proporción relativa de trabajo. Comparamos solo los algoritmos, no el hardware en el que se ejecutan.

Ahora bien, en realidad, O(n) no es exactamente lo que he descrito antes, pero sigue la misma idea de que queremos poder decir que dos cosas son iguales aunque no lo sean.

¿Por qué? Porque en muchos problemas no necesitamos conocer el comportamiento exacto de una función, sino sólo cómo se comporta en general. Por ejemplo, en problemas de convergencia quizá sólo queramos demostrar que algo converge. En este caso no necesitamos conocer el comportamiento local. Si tenemos una función dominante y sabemos que el operador de sustitución de la función dominante es una identidad en el operador límite, entonces podemos calcular y hacer límites mucho más fácilmente. ¡Rápido! ¿Cuál es el límite de 1/x*(cos(x)*3 + 1/x^cos(3x)) cuando x-> oo? Bueno, una aplicación de O(n)-nastics mental puede decir rápidamente que es probablemente 0. En lugar de preocuparse por toda la basura después de 1/x sólo podemos usar 1/x porque, en lo que respecta al límite, ambos son el mismo resultado (el límite los envía a la misma clase de equivalencia).

el límite 3/x es exactamente el mismo que el límite 2/x cuando x->oo. Igual que $3x + 4$ es exactamente la misma expresión que 2x + cos(30.43Pi). Ambas son expresiones lineales. Son EXACTAS bajo ese nivel de abstracción.

Aquí hacemos exactamente lo mismo, pero con tasas de crecimiento de las funciones. Pero no sus tasas de crecimiento exactas, sino su "forma" básica. Por ejemplo, podemos pensar que todas las rectas crecen al mismo ritmo. Igual que todas las parábolas. Aunque $3x^2$ técnicamente crece más rápido que $x^2$ las consideramos iguales porque la tasa de variación del crecimiento es en realidad constante con respecto a la función de base (piénsese en el caso lineal). Por supuesto, entonces podemos combinar clases como términos lineales y cuadráticos. $x^2 + 3x$ . Pues bien, dado que nos ocupamos de x grandes y ya hemos demostrado que $x^2$ dominantes $3x$ (podemos poner cualquier forma más dominante y seguir obteniendo una forma dominante) podemos decir ignorar las partes "sumisas". Ej, $x^2 + 3x == x^2 == 3x^2 = x^2 + cos(3x) == ...$ .

Para recapitular, si tomamos nuestro algoritmo A, tiene una cierta velocidad de ejecución exacta que se podría trazar en un gráfico. Pero si actualizas el hardware ese gráfico cambiará. Aunque probablemente sólo se verá como un gráfico a escala.

Pero digamos que ahora lo ejecutas en un sistema operativo diferente y que ese sistema operativo diferente realiza diferentes tipos de programación, por lo que tu gráfico no tiene el mismo aspecto. PERO existe el mismo patrón general que antes... al menos en carreras largas ¡!

Por tanto, la notación O(n) nos permite hablar de estas cuestiones con mayor precisión. Es una forma de clasificar el conjunto de funciones en una partición/relación de equivalencia útil y luego aplicarlas para encontrar consecuencias más útiles.

En tu mente es "¿Por qué estamos haciendo las cosas tan complejas sólo para hablar de rendimiento en tiempo de ejecución? No tiene sentido". El algoritmo A tarda 10 segundos en calcular S y el algoritmo B tarda 34,432 segundos. El algoritmo A es mejor". Pero esa no es una métrica útil. ¿Por qué es mejor A? ¿Sólo porque se ejecuta más rápido en tu ejemplo? Tal vez no es realmente más rápido, sino que sólo tiene un mejor rendimiento en tiempos de ejecución pequeños (conjuntos de datos pequeños), ya que utiliza el almacenamiento en caché y luego se convierte en el peor algoritmo del planeta. ¿Y entonces qué? Saber que A domina a B en O(n) nos dice que B funciona mejor a largo plazo.

Al pensar en términos de O(n) estás pensando en formas más generales en que las funciones se relacionan (es algo así como con la topología puedes pensar en cómo diferentes funciones son equivalentes (bajo transformaciones homeomórficas)). También estás pensando de forma más "futurista", en el sentido de que tu "hardware" se actualizará automáticamente. Por ejemplo, si diseñas algoritmos basados en fundamentos O(n), puedes saber si tus algoritmos son terribles o no, independientemente de la máquina en la que se ejecuten. A medida que las máquinas se vuelvan más rápidas, los algoritmos seguirán teniendo el mismo "rango" que antes. Así que estás comparando algoritmos en su diseño general y no en aspectos específicos que pueden cambiar en cualquier momento.

Es algo así como la inversa de Taylor. Con las series de Taylor añadimos términos para obtener más y más términos = más y más precisión. Con O(n) queremos hacer lo mismo pero añadir menos y obtener más dominio. Por ejemplo, 1 -> 1 + 2n -> 1 + 2n + n^2 vs 1 + 2n + n^2 -> 2n + n^2 -> n^2.

Aunque la definición técnica y el uso son más "legales", la clave está en transmitir la idea de que se trata de algo diferente y más útil. Lamentablemente, se limitan a dar las definiciones sin explicar por qué fue útil crearlas, y a la mayoría de la gente se le enseñan las definiciones EN VEZ DE las experiencias que condujeron a la definición. [Por ejemplo, no te dan ningún contexto o muy poco, lo que significa que es casi seguro que no lo vas a entender a menos que tengas algunas experiencias que te lo permitan. ]

Gran parte de las matemáticas tienen la necesidad de comparar cosas de forma "vaga". Es decir, hay alguna superposición que queremos entender, pero la forma en que la representamos actualmente dificulta la discusión. Se crea entonces la maquinaria para poder transformar(se construyen transformaciones) el problema en una forma diferente de pensar sobre él.

Es decir, una vez que te das cuenta de que comparar el rendimiento de los algoritmos (que no es más que el comportamiento a largo plazo en matemáticas) es inútil, sigues necesitando alguna forma de compararlos. La necesidad de compare nunca desapareció, sólo la comprensión de que la representación era insuficiente. De ahí que sea necesaria una nueva representación y, por tanto, un nuevo lenguaje, lo que implica definiciones y sus términos. Una vez hecho esto para los algoritmos, llegamos al concepto de representar (hablar de) algoritmos en términos de su "comportamiento a largo plazo". No nos importa la fluctuación inicial ni las aberraciones menores... sólo el comportamiento general a largo plazo.

Las definiciones van definiendo con precisión lo que quieren decir con eso.