5 votos

Función que crece más lento que el registro, uso de exponenciación en lugar de la multiplicación

Estoy tratando de resolver un problema dividiéndolo en trozos, hasta que cada porción es de tamaño 2 o menos, momento en el que cada fragmento es fácil de resolver. Estoy teniendo problemas con la forma de representar matemáticamente cómo muchas de esas divisiones tengo que hacer por algún problema inicial de tamaño n.

Para la mayoría de los problemas que lidiar con, descomponer el problema en la mitad de forma continua hasta alcanzar el trivial tamaños, así que yo diría que hay log(n) divisiones.

Pero con este problema, yo estoy tomando la raíz cuadrada del tamaño de problema en cada fragmento. Por lo que el número de divisiones puede ser representado como "¿cuántas veces debo tomar la raíz cuadrada de n por n se convierte en <=2", o, alternativamente, "¿cuántas veces tengo que square 2 antes de que se convierta >=n". Esta función f(n), sea lo que sea, obviamente crece más lento que log(n), pero no sé de una función con este nombre, ni puedo averiguar cómo iba a representar matemáticamente.

6voto

Alex Bolotov Puntos 249

Si usted Plaza $\displaystyle 2$, $\displaystyle k$ veces, consigues $\displaystyle 2^{2^k}$.

Por lo tanto necesita

$$ 2^{2^k} \ge n$$

es decir

$$ k \ge \log_2 (\log_2 n)$$

y así que usted puede escoger

$$ k = \lceil \log_2 (\log_2 n) \rceil$$

Donde $\displaystyle \log_2$ es a base de $\displaystyle 2$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X