[elcristo]

Hola.

Buscando información, he encontrado un algoritmo que tiene esta complejidad:

\( O((logn)^{c\ log\ log\ log n}) \)

Y no entiendo bien, sobretodo el exponente. Y tampoco sé si esa es una buena complejidad o no para un algoritmo. ¿Alguien puede echarme una mano?

Saludos.

[Luis Fuentes]

Hola

Hola.

Buscando información, he encontrado un algoritmo que tiene esta complejidad:

\( O((logn)^{c\ log\ log\ log n}) \)

Y no entiendo bien, sobretodo el exponente. Y tampoco sé si esa es una buena complejidad o no para un algoritmo. ¿Alguien puede echarme una mano?

Saludos.

Es buena.

Puedes compararla con cualquier otra \( O(f(n)) \) calculando el límite:

\( \displaystyle\lim_{n \to{+}\infty}{}\dfrac{((logn)^{c\ log\ log\ log n}}{f(n)} \)

Si es cero, quiere decir que la complicidad de \( f(n) \) es mayor; si es una constante es que tienen la misma complejidad; si da infinito es la complejidad de \( f(n)  \) es menor.

Saludos.

[elcristo]

Hola, gracias por responder.

Entonces es buena según dices, pero intento calcular límites y no tengo ni idea de qué hacer. Sería:
Sea \( f(x)=logn \)
\( \displaystyle\lim_{n \to{+}\infty}{}\dfrac{((logn)^{c\ log\ log\ log n}}{f(n)}= \displaystyle\lim_{n \to{+}\infty}{}(logn)^{(c\ log \ log \ log n -1)} = \infty  \)

Luego es peor que \( logn \). Pero como es un logaritmo, de seguro es mejor que \( n \) ¿verdad?

Es que ese "\( c\ log\ log\ logn \)" me deja roto. Supongo que es \( c(log(log(logn))) \) ¿no?

Saludos.

[Weip]

Es que ese "\( c\ log\ log\ logn \)" me deja roto. Supongo que es \( c(log(log(logn))) \) ¿no?

Pongas paréntesis o no los pongas da igual porque no hay ambigüedad. Al menos yo lo he visto en muchos sitios sin paréntesis. Pero bueno siempre es bueno ponerlos para estar seguro de lo que se hace.

[Luis Fuentes]

Hola

Hola, gracias por responder.

Entonces es buena según dices, pero intento calcular límites y no tengo ni idea de qué hacer. Sería:
Sea \( f(x)=logn \)
\( \displaystyle\lim_{n \to{+}\infty}{}\dfrac{((logn)^{c\ log\ log\ log n}}{f(n)}= \displaystyle\lim_{n \to{+}\infty}{}(logn)^{(c\ log \ log \ log n -1)} = \infty  \)

Luego es peor que \( logn \). Pero como es un logaritmo, de seguro es mejor que \( n \) ¿verdad?

Si. Por ejemplo si calculas:

\( \displaystyle\lim_{n \to{+}\infty}{}\dfrac{((logn)^{c\ log\ log\ log n}}{n^k}  \)

y llamas \( x=log(n) \), el límite equivale a:

\( \displaystyle\lim_{x \to{+}\infty}{}\dfrac{x^{c\ log\ log x}}{e^{xk}}\leq \dfrac{x^{log(x)}}{e^{kx}}  \)

Tomando \( y=log(x) \):

\( \displaystyle\lim_{y \to{+}\infty}{}\dfrac{e^{y^2}}{e^{ke^y}}=0  \)

Es decir la convergencia es mejor que cualquier polinómica incluso con exponente \( k \) racional.

Saludos.

[elcristo]

Muchas gracias.

Saludos.