¿Qué significa la palabra "escalabilidad" en términos de Big O?

Question

¿Qué significa la palabra "escalabilidad" en términos de Big O?

cálculo
algoritmos
asintóticos
Matemáticas
análisis real
complejidad computacional

matemático

He encontrado muchas fuentes que afirman que:

Los puntos de referencia estiman el tiempo de ejecución, Big O estima la escalabilidad.

Explicaron el significado de "escalabilidad" de la siguiente manera:

La escalabilidad le dice cómo se escala el tiempo de ejecución de su algoritmo. Es decir, cómo crece el tiempo de cálculo cuando aumenta el tamaño de entrada. Para $O\left(n\right)$ duplica el tamaño de la entrada y duplica el tiempo de cálculo. Para $O\left(n^2\right)$ duplica el tamaño de la entrada y cuadruplica el tiempo de cálculo y así sucesivamente.

Es decir, si su algoritmo toma $f(n)$ pasos en el peor de los casos y $f \in O\left(n^2\right)$ , entonces la relación $\frac{f(2n)}{f(n)}$ es igual a $4$ para valores suficientemente grandes de $n$ (usted duplica el tamaño de entrada y cuadruplica el tiempo de cálculo).

Y tenía mucho sentido. Pero recientemente me han mostrado un contraejemplo que demuestra que la declaración anterior es simplemente incorrecta. Considere la función $f\left(n\right) = n^2\left(\cos (n) + 2\right)$ . Podemos ver eso $f \in O\left(n^2\right)$ . Además, para aquellos de ustedes que quieran notar que por $O\left(n^2\right)$ la gente suele querer decir $\Theta\left(n^2\right)$ podemos observar fácilmente que $f \in \Theta\left(n^2\right)$ también:

Pero $f$ no escala como $n^2$ en el sentido de que no podemos afirmar que $\frac{f(2n)}{f(n)}$ es igual a $4$ (incluso aproximadamente) para cualquier valor (incluso grande) de n. Quiero decir, si sabemos que $f \in O\left(n^2\right)$ y si duplicamos su tamaño de entrada, no podemos simplemente cuadruplicar el tiempo de cálculo, porque está mal.

hice una trama de $\frac{f(2n)}{f(n)}$ para que lo visualices:

No parece que esta proporción tienda a 4.

Entonces, mis preguntas son:

¿Por qué la gente explica el significado de "escalabilidad" de esa manera? ¿Hay alguna razón para eso o son técnicamente incorrectos?
Entonces, ¿qué significa esta palabra "escalabilidad"? Entonces, ¿qué estima exactamente Big O (si no es "escalabilidad")?

En general, estoy buscando una explicación matemática pura de eso. Pero no lo pongas demasiado difícil, por favor: todavía estoy aprendiendo el cálculo de una sola variable. ¡Gracias a todos de antemano!

Alcaudón

Hay un problema en que los límites técnicamente no existen. Está claro que

f

$f$ es

Θ (n^{2})

$\Theta(n^2)$ por la idea de acotación, pero la definición de límite señala que mientras que la relación de las funciones definitivamente es finita y distinta de cero, el límite del coseno no está definido en el infinito (oscilación). No estoy seguro aquí, pero incluso puede haber motivos para decir que

f

$f$ no es

O (n^{2})

$O(n^2)$ en absoluto por esta señal.

matemático

@FShrike, gracias por el comentario. Pero

f \in O (n^{2})

$f \in O\left(n^2\right)$ por la definición de Big O.

Alcaudón

La idea de escalabilidad se confunde con la oscilación, pero no hay una conclusión inmediata de escalabilidad a partir de las definiciones de límite (aunque ahora recuerdo que las definiciones de límite usan limit suprema e infima para sortear la idea de que los límites regulares no existen, así que tomo de vuelta algo de lo que dije en el comentario anterior)

ian

1. Ejemplos como este donde

f \in Θ (g)

$f \in \Theta(g)$ pero

f / g

$f/g$ es oscilatorio como

n \to \infty

$n \to \infty$ no son comunes en la práctica real. De improviso, lo único que viene a la mente con este comportamiento es la FFT, e incluso eso tiene una escala fija si trabaja solo con potencias de 2. 2. La escalabilidad aún expresa la tasa de crecimiento de la función de una manera aproximada, cuánto más grande se vuelve cuando aumenta la entrada por un montón. Big Theta todavía te da esta descripción aproximada. Pero tienes razón en que solo sabiendo, digamos,

f \in Θ (n^{2})

$f \in \Theta(n^2)$ no te dice eso

f (2 n) / f (n)

$f(2n)/f(n)$ tenderá hacia

4

$4$ .

ian

En el contexto de la teoría de la complejidad, en particular, a las personas generalmente les importan los peores casos o los casos típicos. Los peores casos en su situación significarían "comparar dos problemas donde

n

$n$ está cerca de un múltiplo de

2 π

$2\pi$ "; los casos típicos significarían "comparar dos problemas donde

n

$n$ está cerca de un múltiplo impar de

π / 2

$\pi/2$ ".

matemático

@Ian, ¡Gracias por el comentario! En el último comentario, afirmas que

n^{2} (c o s (n) + 2)

$n^2\left(cos(n) + 2\right)$ no puede ser el peor de los casos, porque

3 n^{2}

$3n^2$ es aun peor?

ian

Quiero decir, si el tiempo de ejecución real es

n^{2} (\cos (n) + 2)

$n^2(\cos(n)+2)$ entonces el peor de los casos para

n

$n$ en un intervalo de longitud

2 π

$2\pi$ va a ser cuando

n

$n$ es múltiplo de

2 π

$2\pi$ y en ese caso tienes

3 n^{2}

$3n^2$ .

matemático

@Ian, pero según tengo entendido, no hay tiempo de ejecución real si no especifica el caso primero (peor, promedio, mejor). A partir de este punto cuando lo clasificaste como peor, deduces la función

f (n)

$f(n)$ que representan una serie de pasos tomados para la entrada de longitud en el peor de los casos

n

$n$ . Pero, ¿cómo puede ir más allá y especificar puntos separados del formulario?

2 π k

$2πk$ para representar el comportamiento del peor de los casos, si ya tenemos la función

f

$f$ que representa el peor caso de comportamiento?

ian

quiero decir que

n

$n$ es el tamaño de entrada real y

f (n)

$f(n)$ el tiempo de ejecución real, y

f (n)

$f(n)$ fluctúa porque de alguna manera los números se acercan a los múltiplos enteros impares de

π

$\pi$ son mucho más fáciles de manejar que los números cercanos a múltiplos enteros pares de

π

$\pi$ (una situación inusual en sí misma). entonces lo peor

n

$n$ 's de un "orden de magnitud" dado son aquellos cercanos

2 π k

$2\pi k$ , por lo que si desea estudiar el crecimiento del peor de los casos, mire

n = r o u n d (2 π k), k = 1, 2, \dots

$n=\mathrm{round}(2\pi k),k=1,2,\dots$ (es decir

6, 13, 19

$6,13,19$ etc.)

matemático

@Ian, ¿pero estás de acuerdo en que cuando consideramos la función

f (n)

$f(n)$ eso ya significa cada entrada

n

$n$ debe ser lo peor? Porque

f (n)

$f(n)$ es, por su definición, toma solo las entradas del peor de los casos

ian

No, estoy hablando de los peores valores locales de

n

$n$ (que generalmente no es algo a considerar, pero es algo en su caso).

Respuestas (2)

¿Qué significa la palabra "escalabilidad" en términos de Big O?

Hay un problema en que los límites técnicamente no existen. Está claro que $f$ es $\Theta(n^2)$ por la idea de acotación, pero la definición de límite señala que mientras que la relación de las funciones definitivamente es finita y distinta de cero, el límite del coseno no está definido en el infinito (oscilación). No estoy seguro aquí, pero incluso puede haber motivos para decir que $f$ no es $O(n^2)$ en absoluto por esta señal.
@FShrike, gracias por el comentario. Pero $f \in O\left(n^2\right)$ por la definición de Big O.
La idea de escalabilidad se confunde con la oscilación, pero no hay una conclusión inmediata de escalabilidad a partir de las definiciones de límite (aunque ahora recuerdo que las definiciones de límite usan limit suprema e infima para sortear la idea de que los límites regulares no existen, así que tomo de vuelta algo de lo que dije en el comentario anterior)
1. Ejemplos como este donde $f \in \Theta(g)$ pero $f/g$ es oscilatorio como $n \to \infty$ no son comunes en la práctica real. De improviso, lo único que viene a la mente con este comportamiento es la FFT, e incluso eso tiene una escala fija si trabaja solo con potencias de 2. 2. La escalabilidad aún expresa la tasa de crecimiento de la función de una manera aproximada, cuánto más grande se vuelve cuando aumenta la entrada por un montón. Big Theta todavía te da esta descripción aproximada. Pero tienes razón en que solo sabiendo, digamos, $f \in \Theta(n^2)$ no te dice eso $f(2n)/f(n)$ tenderá hacia $4$ .
En el contexto de la teoría de la complejidad, en particular, a las personas generalmente les importan los peores casos o los casos típicos. Los peores casos en su situación significarían "comparar dos problemas donde $n$ está cerca de un múltiplo de $2\pi$ "; los casos típicos significarían "comparar dos problemas donde $n$ está cerca de un múltiplo impar de $\pi/2$ ".
@Ian, ¡Gracias por el comentario! En el último comentario, afirmas que $n^2\left(cos(n) + 2\right)$ no puede ser el peor de los casos, porque $3n^2$ es aun peor?
Quiero decir, si el tiempo de ejecución real es $n^2(\cos(n)+2)$ entonces el peor de los casos para $n$ en un intervalo de longitud $2\pi$ va a ser cuando $n$ es múltiplo de $2\pi$ y en ese caso tienes $3n^2$ .
@Ian, pero según tengo entendido, no hay tiempo de ejecución real si no especifica el caso primero (peor, promedio, mejor). A partir de este punto cuando lo clasificaste como peor, deduces la función $f(n)$ que representan una serie de pasos tomados para la entrada de longitud en el peor de los casos $n$ . Pero, ¿cómo puede ir más allá y especificar puntos separados del formulario? $2πk$ para representar el comportamiento del peor de los casos, si ya tenemos la función $f$ que representa el peor caso de comportamiento?
quiero decir que $n$ es el tamaño de entrada real y $f(n)$ el tiempo de ejecución real, y $f(n)$ fluctúa porque de alguna manera los números se acercan a los múltiplos enteros impares de $\pi$ son mucho más fáciles de manejar que los números cercanos a múltiplos enteros pares de $\pi$ (una situación inusual en sí misma). entonces lo peor $n$ 's de un "orden de magnitud" dado son aquellos cercanos $2\pi k$ , por lo que si desea estudiar el crecimiento del peor de los casos, mire $n=\mathrm{round}(2\pi k),k=1,2,\dots$ (es decir $6,13,19$ etc.)
@Ian, ¿pero estás de acuerdo en que cuando consideramos la función $f(n)$ eso ya significa cada entrada $n$ debe ser lo peor? Porque $f(n)$ es, por su definición, toma solo las entradas del peor de los casos
No, estoy hablando de los peores valores locales de $n$ (que generalmente no es algo a considerar, pero es algo en su caso).

especialmente lima · Answer 1

Este (muy bonito) ejemplo es bastante inusual - en la práctica funciona $f(n)$ que en realidad surgen y son $\Theta(n^2)$ normalmente satisfacen $f(n)/n^2$ tiende a algún límite positivo (en lugar de simplemente estar acotado de $0$ y $\infty$ ). Así que la versión simplificada de escalabilidad - $\lim_{n\to\infty}f(2n)/f(n)$ - existe y es $4$ .

Sin embargo, incluso para su función, todavía hay un sentido razonable en el que duplicar $n$ , en promedio, aumenta $f(n)$ por un factor de $4$ . ¿Qué podemos entender por "en promedio"? Bueno, para sacar un promedio necesitas duplicar más de una vez. Si duplicas dos veces para ir de $f(n)$ a $f(4n)$ entonces el factor de escala promedio de las dos duplicaciones que tiene sentido es la media geométrica (porque está tratando de aproximarse por crecimiento geométrico), es decir $\sqrt{f(4n)/f(n)}$ . Ahora bien, esto tampoco tiende a un límite, pero $\sqrt[k]{f(2^kn)/f(n)}$ , es decir, el factor de escala promedio (geométrico) de $k$ duplicaciones, tiende a un límite como $k\to\infty$ , cual es $4$ .

¡Gracias por la respuesta! ¿Pero no parece que acabamos de inventar de la nada una forma de justificar el significado original de la palabra "escala"?
Además, ¿por qué la media aritmética es peor en este caso? Me parece tan razonable como lo es la media geométrica.
@mathgeek Es básicamente porque si escalamos por un factor $x$ y luego escalar por un factor $y$ , entonces la escala general es $xy$ no $x+y$ . La idea de sacar un promedio es "¿qué lista de $k$ cosas idénticas serían más como esta lista de $k$ cosas diferentes?" Aquí escalando por $k$ diferentes factores deberían dar el mismo resultado general que la escala por el factor "promedio" $k$ veces, y eso funciona si como "promedio" significa la media geométrica.
¡No podía esperar una explicación mejor que esta! ¡Gracias! Pero difícilmente puedo imaginar a la gente pensando en todos estos cálculos cuando dicen cosas como que el tiempo de ejecución crece "del orden del cuadrado del tamaño de la entrada". ¿Podría aclarar lo que esas personas piensan (lo que realmente quieren decir) al decirlo y si es legítimo decirlo sobre $f$ , dado $f \in O(n^2)$ ?
Todavía es correcto, solo puede fallar en el nivel de comparación de dos valores de funciones particulares si $f$ es raro. Y realmente no puedo enfatizar lo suficiente lo atípico que es su ejemplo en el análisis asintótico real, especialmente en la teoría de la complejidad.
@ Jean-ClaudeArbaut No veo por qué es engañoso. Estoy hablando específicamente del ejemplo de OP, que (como dice OP específicamente) es un ejemplo de una función que es $\Theta(n^2)$ pero parece no escalar como se esperaba. Si sólo sabes que una función es $O(n^2)$ , luego en el segundo párrafo básicamente necesitas reemplazar $\lim$ por $\limsup$ y $4$ por $\leq 4$ .

Perezoso · Answer 2

Perezoso

Los símbolos de Landau no se preocupan por el comportamiento exacto de las funciones. $f\in O(g)$ significa que para grandes $x$ tenemos $f$ escalas a lo sumo tan malas como $g$ en el sentido de que $f$ está acotado por un múltiplo de $g$ .

Cuando las personas lo explican de la forma en que lo mencionaste, lo están simplificando demasiado, probablemente asumiendo que la otra parte no entendería de lo que uno está hablando.

matemático

¡Gracias por la respuesta! Pero si miras mi primer gráfico, notarás que

f

$f$ escamas peor que

n^{2}

$n^2$ a intervalos

(10; 12)

$\left(10;\ 12\right)$ Por ejemplo. Por lo tanto, no "escala COMO MÁS tan mal como

g

$g$ ".

Alcaudón

@mathgeek Consideramos límites como

n \to \infty

$n\to\infty$ en la definición estándar, no como

n \to (10, 12)

$n\to(10,12)$

matemático

Solo di un ejemplo para que puedas observarlo fácilmente desde la trama. Pero estoy seguro de que puede ver que mi declaración es válida para cualquier

n

$n$ (puedes hacerlo tan grande como quieras).

Perezoso

@mathgeek Esa es una de las advertencias con la notación de Landau. Escalar es un término que usamos para el argumento que crece, pero no especificamos qué tan grande sería. Tenga en cuenta que si

f

$f$ es continuo y

g

$g$ es continuo y en ninguna parte

0

$0$ entonces en cualquier intervalo cerrado siempre encontramos un

c

$c$ con

f \leq c g

$f\leq cg$ en ese intervalo (mín./máx. de funciones continuas en conjuntos compactos). E incluso entonces, la definición de los símbolos de Landau siempre especifica: Para todos

x > x_{0}

$x>x_0$ por alguna arbitraria

x_{0}

$x_0$ . Básicamente, no nos importan los valores finitos.

Perezoso

Puedes pensar en esto de esta manera: Si

f \in O (g)

$f\in O(g)$ entonces la asintótica

lim sup \frac{f (x)}{g (x)}

$\limsup\frac{f(x)}{g(x)}$ es finito Si

f \in Θ (g)

$f\in\Theta(g)$ Después también

0 < lim inf \frac{f (x)}{g (x)}

$0<\liminf \frac{f(x)}{g(x)}$ .

matemático

Sí, su último comentario es la definición, pero desafortunadamente no explica el significado de la palabra "escala" y por qué tiene sentido a la luz de mi pregunta publicada.

Perezoso

Bueno, el escalado generalmente no se usa en matemáticas puras, sino en el contexto de algoritmos y demás. Y aquí escalar solo significa: si aumento la entrada, ¿cómo cambia el tiempo requerido? Por ejemplo, si tuviera que ordenar una lista de tamaño

n

$n$ los mejores algoritmos que funcionan sin grandes suposiciones tienen un orden de

n \log n

$n\log n$ comparaciones Entonces, si aumento el tamaño de mi lista, el esfuerzo requerido aumenta un poco más que linealmente, pero menos que cuadráticamente. Por supuesto, hay varias cosas que puede considerar: ¿El mejor de los casos? ¿Peor de los casos? caso promedio?

matemático

De acuerdo, cuando señaló que "el escalado generalmente no se usa en matemáticas puras, sino en el contexto de los algoritmos", comenzó a tener sentido. Diste un ejemplo de algoritmo ejecutándose en

O (\log n)

$O\left(\log n\right)$ tiempo. ¿Podría aclarar qué quiere decir con "aumenta cuadráticamente"? Por favor, tenga en cuenta el ejemplo de la explicación incorrecta de "aumenta cuadráticamente" que di en mi pregunta.

¿Qué significa la palabra "escalabilidad" en términos de Big O?

matemático

Alcaudón

matemático

Alcaudón

ian

ian

matemático

ian

matemático

ian

matemático

ian

Respuestas (2)

especialmente lima

matemático

matemático

especialmente lima

matemático

ian

especialmente lima

Perezoso

matemático

Alcaudón

matemático

Perezoso

Perezoso

matemático

Perezoso

matemático

¿Qué te dice Big O realmente?

tiempo de ejecución del algoritmo dada la complejidad del tiempo

Complejidad del algoritmo: bucle for dentro del bucle while; decreciendo por el factor 2

¿Cómo se calcula el valor de un límite multivariable?

¿Cuál es la complejidad del tiempo cuando se muestrean uniformemente las entradas bbb sin reemplazo de las entradas nnn?

Tiempo esperado de Quicksort

¿Spivak usa una propiedad en su propia prueba?

Débil continuidad absoluta de las medidas

¿Contraejemplo de "diferenciable implica continuo"?

Integrales de Darboux con partición bisecada