¿Qué podemos decir acerca de la tasa de crecimiento de una función de crecimiento más rápido de todos los polinomios?

Question

Supongamos $f: \mathbb{R} \rightarrow \mathbb{R}$ satisface lo siguiente:

$$ \forall k \in \mathbb{N} \hspace{5pt} \lim_{t \rightarrow \infty} \frac{t^k}{f(t)} = 0.$$

Podemos deducir una mayor tasa de crecimiento $f$? Por ejemplo (sé que esto es muy esperanzador - solo estoy dando un ejemplo de la clase de cosas que quiero decir) podemos decir

$$ \limsup_{t \rightarrow \infty} \frac{e^t}{f(t)} < \infty \hspace{5pt}?$$

Muchas gracias por tu ayuda.

Answer 1

Si $g$ es cualquier función que crece más rápido que todos los polinomios, a continuación, $\sqrt{g}$ es otro ejemplo de función, que crece más lento de lo $g$. Así que nada, como su declaración de que jamás podría ser verdad, incluso si usted sustituye $e^t$ con alguna otra función.

En general, las tasas de crecimiento de las funciones son extremadamente denso - dio ninguna de las dos categorías de la tasa de crecimiento, donde uno es estrictamente mayor que el otro, sólo puede siempre inventan una función cuyo crecimiento es intermedia entre la de ellos (excepto cuando su incapacidad para hacerlo es tautológica; por ejemplo, las categorías son "funciones polinómicas" y "funciones que crecen más rápido que los polinomios").

Answer 2

No hay mucho que se puede decir acerca de la tasa de crecimiento de $f$. Específicamente, no hay más lento $f$ que crece más rápido que cualquier polinomio. Por ejemplo, $x^{\log(x)}$, $x^{\log(\log(x))}$, $x^{\log(\log(\log(x)))}$, etc. todos crecen más rápido que cualquier polinomio.

Un equivalente de la caracterización de su función es que el $f\in x^{\omega(1)}$ donde $\omega(1)$ significa que va hasta el infinito. Estas funciones son ampliamente referenciados en ciencias de la computación como son las funciones que describen la complejidad computacional de "ineficiente" de los algoritmos.