0

Tengo esta tarea donde tengo que indicar y justificar la función de complejidad y el orden de complejidad del algoritmo del siguiente método recursivo que analiza la paridad de un número n.

public static boolean esPar(int n) {
    if (n == 0) {
    return true;
    }
    return !esPar(n−1);
    }

Y escrbir otro método que haga exactamente lo mismo que el método esPar(int n) pero con una complejidad mejor. Justificando el mismo con mis palabras y/o lenguaje matemático. Tengo mis dudas de como se, porque no me quedó muy claro el tema visto en clase. Puse que el Orden de complejidad era O(1) pero me dijo el profesor que estaba mal.

1 respuesta 1

3

Para conocer el orden de complejidad de la función calcularemos el costo de la función. Vamos a tomar el costo en base al número de veces que tiene que entrar en recursividad antes de obtener el resultado.

Sea C(n) el costo de calcular la paridad de n utilizando la función EsPar(n). Para ello, vamos a darle algunos valores a n.

1) n=0 -> C(0) = 0
2) n=1 -> C(1) = 1 + C(0) =>  C(1) = 1 + 0 => C(1) = 1
3) n=2 -> C(2) = 1 + C(1)
4) n+1 -> C(n+1) = 1 + C(n)

Por 4 se observa que el costo es una funcion lineal puesto crece proporcionalmente al incremento de n:

C(n+1) = 1 + C(n) // por 4
       = 1  + n   // por 1 y 2
       = n  +  1   // por algebra

Por lo tanto es costo de la función es lineal correspondiendole un orden de complejidad O(n).

Veamos una la función esPar2 para calcular la paridad de n:

public static boolean esPar2(int n) {
    return (n%2)==0;
}

Está función toma el mismo tiempo para cualquier n, es decir, tiene un costo constante y por lo tanto un orden de complejidad O(1).

En resumen:

EsPar(n) -> O(n)
EsPar2(n) -> O(1)

Espero que hayas entendido lo que el orden de complejidad y que respondas la tarea con tus propias palabras porque te pueden preguntar algo que no he puesto.

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.