¿Orden de las pruebas de crecimiento?

Question

Me preguntaba cómo hace la gente para mostrar las pruebas con órdenes de crecimiento. Actualmente, tengo las siguientes funciones y sé en qué orden van, pero no estoy seguro de cómo demostrarlas. Simplemente las puse en una aplicación de gráficos que vi en Internet y el gráfico mismo mostraba obviamente el crecimiento.

$$\begin{align} & 2^{\sqrt{\log n}}\\ & 2^n\\ & n^{4/3}\\ & n \log^3 n\\ & n^{ \log n}\\ & 2^{2^n}\\ & 2^{n^2} \end{align}$$

Por ejemplo, sé que $2^{2^n}$ tiene la mayor tasa de crecimiento, con $2^{n^2}$ llegando en segundo lugar. Lo sé porque si introduzco el valor de $5$ se convierte en $2^{32}$ vs $2^{25}$ , $6$ es $2^{64}$ vs $2^{36}$ . Pero, ¿es esa la prueba en sí misma?

En cuanto a los de impar fuera, no tengo ni idea de cómo podría mostrar una comparación de prueba de $n^{4/3}$ vs $n\log^3 $ n vs $2^n$ etc.

Answer 1

Reglas generales que se mantienen para un tamaño suficientemente grande $n$ :

$$\begin{align} &\log^c(n) \leq n^{\epsilon}, \quad \text{ for any } \epsilon > 0, \quad \text { and any constant } c \\ \\ &n^k \leq k^n, \qquad \text{where } k \text{ is any constant } k > 1 \end{align} $$

Como Chris señaló anteriormente, podemos escribir esto como

$$ A \ll \log^c (n) \ll n^{\epsilon} \ll k^n $$

Para demostrar realmente estas reglas, basta con calcular los límites (suponiendo que se sepa calcular). Para ver que $\log (n) \ll n^{\varepsilon}$ por ejemplo, sólo hay que tener en cuenta que

$$ \lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{n^{-1}}{\epsilon n^{\epsilon - 1}} = 0 = \lim_{n \to \infty} \frac{1}{\epsilon n^{\epsilon}} = 0. $$

donde $A$ y $c$ son constantes, $\epsilon > 0$ y $k$ es un número real tal que $k > 1$ .

Si quiere demostrar que $\log^c(n) \ll n^{\epsilon}$ para cualquier número entero positivo $c$ entonces sólo hay que tener en cuenta que

$$ \lim_{n \to \infty} \frac{\log^c (n)}{n^\epsilon} \leq \left( \lim_{n \to \infty} \frac{\log (n)}{n^{\epsilon/c}} \right) \dots \left( \lim_{n \to \infty} \frac{\log(n)}{n^{\epsilon/ c}}\right) = 0 $$ por lo que mostramos arriba. En realidad podemos tomar $c$ ser cualquier número real arbitrario y lo anterior sigue siendo válido. Esto es fácil de ver, ya que todo número real es menor o igual que un número entero (de hecho, infinitos). Te dejo que demuestres que $n \log^3 (n) \ll n^{4/3}$ por ejemplo. Las funciones más complicadas funcionan de la misma manera, pero puede que tengamos que ser ligeramente creativos a la hora de evaluar los límites.

Espero que esto ayude.