Cadena infinita de grandes

Primero, déjame escribir la definición de grande $O$ solo para hacer las cosas explícitas.

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ tal que $0\le f(n)\le cg(n), \forall n\ge n_0$

Digamos que tenemos un número finito de funciones: satisfactoria: $f_1,f_2,\dots f_n$

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

Por transitividad de , tenemos que: $O$ $O(f_1)\subseteq O(f_n)$

¿Esto se cumple si tenemos una cadena infinita de ? En otras palabras, ¿ ? $O's$ $O(f_1) \subseteq O(f_\infty)$

Tengo problemas para imaginar lo que está pasando.

asymptotics landau-notation saadtaame
fuente

Respuestas:

Primero tenemos que aclarar lo que queremos decir con "¿esto se cumple si tenemos una cadena infinita?". Nosotros interpretamos como una secuencia infinita de funciones tal que para todo tenemos . Tal secuencia podría no tener una última función. $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ $i$ $f_i(n) = O(f_{i+1}(n))$

Podemos observar el límite de las funciones en la secuencia, es decir, . Sin embargo, es posible que el límite no exista. E incluso en el caso de que exista, es posible que no tengamos . Por ejemplo, considere la secuencia de funciones . Para cada , y, por lo tanto, . Sin embargo, tanto . $f_\infty(n) = \lim_{i\to \infty} f_i(n)$ $f_1(n) = O(f_\infty(n))$ $f_i(n) = \frac{n}{i}$ $i$ $f_i(n)=\Theta(n)$ $f_i(n) = O(f_{i+1}(n))$ $f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$ $f_1(n) \neq O(f_\infty(n))$

Por otro lado, podemos ver el límite de la secuencia de las clases que no necesita ser igual a la clase del límite de las funciones . Tenemos , por lo tanto, y para todo . El límite superior contiene todos los elementos (funciones en este caso) que ocurren infinitamente y el límite inferior contiene todos los elementos que ocurren en todos para algunos $f_i \in \mathcal O(f_{i+1})$ $\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$ $f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$ $j$ $\mathcal O(f_i), i \ge n_0$ $n_0$ (que puede depender del elemento). Dado que la secuencia de clases está aumentando monotónicamente, existen y son iguales. Esto justifica el uso de . $\lim$

frafl
fuente

Hay dos series: una de funciones (que pueden converger o no) y una de conjuntos (donde cada conjunto es un superconjunto del anterior; esta es la razón por la cual esta serie converge; vea la definición de lim inf y lim sup para conjuntos) . La primera parte responde a la pregunta sin la parte , la segunda parte responde negativamente a la parte (si es algún tipo de limas).

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

f_{\infty}

$f_\infty$

frafl

¿Qué pasa si el número de términos es incontable? :)

SamM

¿Usando un buen orden o quiere reemplazar la serie por algo más continuo? :)

frafl

@Kaveh Muchas gracias, ahora tiene mucho sentido. Si pudieras justificar el uso de límites y lo que significa esa cosa limitada, eso completará mi comprensión.

saadtaame

@saadtaame: ¿Tal vez sea porque la pregunta anterior todavía no pregunta qué quieres saber? Si no recuerdo mal, agregaste debido a que un comentario lo sugirió. Si proporciona algún contexto, tal vez alguien podría reformular la pregunta nuevamente.

f_{\infty}

$f_\infty$

frafl

Sí, es posible tener una cadena infinita.

Estoy seguro de que ya está familiarizado con algunos ejemplos: Aquí tiene una cadena infinita: polinomios de grado creciente. ¿Puedes ir más lejos? ¡Seguro! Un exponencial crece más rápido (asintóticamente hablando) que cualquier polinomio. Y, por supuesto, puede continuar:

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (x^{42}) \subseteq \dots O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x)$

O (e^{x}) \subseteq O (x e^{x}) \subseteq O (e^{2 x}) \subseteq O (e^{e^{x}}) \subseteq \dots

$O(\mathrm{e}^x) \subseteq O(x\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

También puedes construir una cadena infinita en la otra dirección. Si entonces (atendiendo a las funciones positivas, ya que por aquí discutimos la asintótica de las funciones de complejidad) Entonces tenemos por ejemplo: $f = O(g)$ $\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$

O (x) \subseteq O (x^{2}) \subseteq \dots \subseteq O (\frac{e^{x}}{x^{2}}) \subseteq O (\frac{e^{x}}{x}) \subseteq O (e^{x})

$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x)$

De hecho, dada cualquier cadena de funciones , puede construir una función que crezca más rápido que todas ellas. (Supongo que las son funciones desde a .) Primero, comience con la idea . Eso puede no funcionar porque el conjunto puede ser ilimitado. Pero como solo estamos interesados en el crecimiento asintótico, es suficiente comenzar de a poco y crecer progresivamente. Tome el máximo sobre un número finito de funciones. $f_1, \ldots, f_n$ $f_\infty$ $f_i$ $\mathbb{N}$ $\mathbb{R}_+$ $f_\infty(x) = \max \{f_n(x) \mid n \in\mathbb{N}\}$ $\{f_n(x) \mid n \in\mathbb{N}\}$

f_{\infty} (x) = max {f_{n} (x) ∣ 1 \leq n \leq N} if N \leq x < N + 1

$f_\infty(x) = \max \{f_n(x) \mid 1 \le n \le N \} \qquad \text{if $N \le x \lt N+1$}$ Luego, para cualquier , , ya que . Si desea una función que crezca estrictamente más rápido ( ), tome .

N

$N$

f_{N} \in O (f_{\infty})

$f_N \in O(f_\infty)$

\forall x \geq N, f_{\infty} (x) \geq f_{N} (x)

$\forall x \ge N, f_\infty(x) \ge f_N(x)$

f_{\infty} = o (f_{\infty}^{'})

$f_\infty = o(f_\infty')$

f_{\infty}^{'} (x) = x \cdot (1 + f_{\infty} (x))

$f_\infty'(x) = x \cdot (1 + f_\infty(x))$

Gilles 'SO- deja de ser malvado'
fuente

Todas estas respuestas (la suya y la otra), se basan en asumir que sabemos lo que sucede en el infinito, no son satisfactorias para mí, no sé sobre el OP (por qué no deberíamos tener un grupo cerrado con un tamaño infinito) ?)

@SaeedAmiri Lo siento, no entiendo tu comentario: ¿qué quieres decir con "sabemos lo que sucede en el infinito, no son satisfactorios para mí"?

Gilles 'SO- deja de ser malvado'