Autor Tema: Algoritmo y complejidad para averiguar si n es potencia pura.

0 Usuarios y 1 Visitante están viendo este tema.

11 Enero, 2017, 07:24 pm
Leído 2018 veces

JorgeFC

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 200
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
¿Cómo puedo dar un algoritmo de complejidad O(\( (logn)^4 \)) para averiguar si un entero positivo n es potencia pura?

En caso de que lo sea me piden escribirlo como potencia de un entero positivo.
Me han dicho que la idea sería la misma que para calcular la parte entera de la raíz cuadrada de n, pero no lo he entendido bien.

16 Enero, 2017, 12:01 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,834
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

¿Cómo puedo dar un algoritmo de complejidad O(\( (logn)^4 \)) para averiguar si un entero positivo n es potencia pura?

En caso de que lo sea me piden escribirlo como potencia de un entero positivo.
Me han dicho que la idea sería la misma que para calcular la parte entera de la raíz cuadrada de n, pero no lo he entendido bien.

Mira por aquí:

http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-another-na

Saludos.