0

El algoritmo siguiente no hace nada en específico, pero es similar a otro y este es más sencillo de entender y esta escrito en JavaScript. La entrada del algoritmo es un número entero mayor que cero:

function my_func(n) {
    while (n % 2 == 0) {
        n = n / 2;
    }
    if (n < 2) {
        return;
    }
    my_func((n - 1) / 2);
    my_func((n + 1) / 2);
}

¿Cuál es su complejidad algorítmica y porque?

He buscado en Internet algún algoritmo parecido con su complejidad, pero no he encontrado nada.

2
  • Y por que no determinas su complejidad?
    – Christian
    Commented el 15 may. 2021 a las 23:02
  • @Christian Para este caso en particular no se como determinarlo, ni encuentro ningún ejemplo en Internet. Pero me da la sensación de que su complejidad es lineal, porque si lo doy como entrada un número muy grande, parece que no terminara nunca. Commented el 16 may. 2021 a las 0:18

2 respuestas 2

0

en realidad el algoritmo no solo divide entre dos

En primer lugar recibe un número, que suponiendo que sea entero, lo evalúa por si es par.

Si es par, entra en el bucle y los va diviendo entre dos hasta que sale del bucle por ser menor que 2 y retorna el resultado.

Si el número no es par, continua el programa sin entrar en el bloque while

Llega a la primera instrución de recursividad. Toma el número, le resta 1 y lo divide entre dos pasando a llamar a la función.

Ahora el número ya es par, por lo que entrará en el bucle while hasta que al ser dividido sucesivamente entre dos, sea menor que dos y salga del bucle devolviendo el resultado, que siempre será 1.

continuará el programa, volverá a llegar a la primera instrucción después del bucle while, cogerá de nuevo el número y dependiendo donde se haya declarado la variable n, podría entrar en un bucle infinito.

No se si me equivoco, pero es lo que creo

1
  • 2
    Si, no te equivocas. Pero si la entrada es un entero positivo mayor que cero, no entra en un bucle infinito. En las llamadas recursivas resta 1 o suma 1, porque el número es impar y el antecesor y el sucesor de un numero impar es siempre par. Si al algoritmo le quito una llamada recursiva, su complejidad es logaritmica. Pero me da la sensación de que la complejidad del algoritmo es lineal. Commented el 16 may. 2021 a las 0:15
0

Cada vez que lo mandas a llamar, n se parte a la mitad, supongamos que empiezas en n = 2048

En la primera iteración: n = 1024

Despues: n = 512

Luego: n = 256

n = 124

n = 64

n = 32

n = 16

n = 8

n = 4

n = 2

n = 1

Sí te das cuenta estas son las potencias de dos, sí despejamos la n nos queda como log2(n) que es lo mismo que log(n)

1
  • Ese sería el caso si tuviera una sola llamada recursiva. En este caso tiene 2 llamadas. así que su complejidad es mayor. Commented el 16 may. 2021 a las 0:19

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.