Determinación de la complejidad de funciones recursivas (notación Big O)

Hola, encontramos la solución a tu pregunta, desplázate y la obtendrás aquí.

Solución:

La complejidad del tiempo, en notación Big O, para cada función:

---

int recursiveFun1(int n)

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);

Esta función se llama recursivamente n veces antes de llegar al caso base, por lo que su O(n)llamado a menudo lineal.

---

int recursiveFun2(int n)

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);

Esta función se llama n-5 para cada vez, por lo que deducimos cinco de n antes de llamar a la función, pero n-5 también es O(n). (En realidad llamado orden de n/5 veces. Y, O(n/5) = O(n) ).

---

int recursiveFun3(int n)

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);

Esta función es log(n) base 5, por cada vez que dividimos por 5 antes de llamar a la función por lo que es O(log(n))(base 5), a menudo llamado logarítmico y la mayoría de las veces, la notación Big O y el análisis de complejidad utilizan la base 2.

---

void recursiveFun4(int n, int m, int o)

    if (n <= 0)
    
        printf("%d, %dn",m, o);
    
    else
    
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    

Aqui esta O(2^n)o exponencialya que cada llamada de función se llama a sí misma dos veces a menos que haya sido recursiva norte veces.

---

int recursiveFun5(int n)

    for (i = 0; i < n; i += 2) 
        // do something
    

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);

Y aquí el ciclo for toma n/2 ya que estamos aumentando en 2, y la recursividad toma n/5 y dado que el ciclo for se llama recursivamente, por lo tanto, la complejidad del tiempo está en

(n/5) * (n/2) = n^2/10,

debido al comportamiento asintótico y las consideraciones del peor de los casos o el límite superior por el que se esfuerza Big O, solo estamos interesados ​​​​en el término más grande, por lo que O(n^2).

---

Suerte en tus parciales 😉

Para el caso en que n <= 0, T(n) = O(1). Por lo tanto, la complejidad temporal dependerá de cuándo n >= 0.

Consideraremos el caso n >= 0 en la parte de abajo.

1.

T(n) = a + T(n - 1)

donde a es una constante.

Por inducción:

T(n) = n * a + T(0) = n * a + b = O(n)

donde a, b son algunas constantes.

2.

T(n) = a + T(n - 5)

donde a es una constante

Por inducción:

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

donde a, b son constantes y k <= 0

3.

T(n) = a + T(n / 5)

donde a es una constante

Por inducción:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

donde a, b son algunas constantes

4.

T(n) = a + 2 * T(n - 1)

donde a es una constante

Por inducción:

T(n) = a + 2a + 4a + ... + 2^(n-1) * a + T(0) * 2^n 
     = a * 2^n - a + b * 2^n
     = (a + b) * 2^n - a
     = O(2 ^ n)

donde a, b son algunas constantes.

5.

T(n) = n / 2 + T(n - 5)

donde n es una constante

Volver a escribir n = 5q + r donde q y r son enteros y r = 0, 1, 2, 3, 4

T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)

Tenemos q = (n - r) / 5y como r < 5, podemos considerarlo una constante, por lo que q = O(n)

Por inducción:

T(n) = T(5q + r)
     = (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 +  T(r)
     = 5 / 2 * (q + (q - 1) + ... + 1) +  1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)

Como r < 4, podemos encontrar alguna constante b tal que b >= T(r)

T(n) = T(5q + r)
     = 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
     = 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
     = O(n ^ 2)

Una de las mejores formas que encuentro para aproximar la complejidad del algoritmo recursivo es dibujar el árbol de recursión. Una vez que tenga el árbol recursivo:

Complexity = length of tree from root node to leaf node * number of leaf nodes

1. La primera función tendrá una longitud de n y número de nodo hoja 1 por lo que la complejidad será n*1 = n

2. La segunda función tendrá la longitud de n/5 y número de nodos hoja de nuevo 1 por lo que la complejidad será n/5 * 1 = n/5. Debe aproximarse a n

3. Para la tercera función, ya que n se divide por 5 en cada llamada recursiva, la longitud del árbol recursivo será log(n)(base 5)y el número de nodos hoja nuevamente 1, por lo que la complejidad será log(n)(base 5) * 1 = log(n)(base 5)

4. Para la cuarta función, dado que cada nodo tendrá dos nodos secundarios, el número de nodos hoja será igual a (2^n) y la longitud del árbol recursivo será n por lo que la complejidad será (2^n) * n. Pero desde n es insignificante frente a (2^n)se puede ignorar y solo se puede decir que la complejidad es (2^n).

5. Para la quinta función, hay dos elementos que introducen la complejidad. Complejidad introducida por la naturaleza recursiva de la función y complejidad introducida por for bucle en cada función. Haciendo el cálculo anterior, la complejidad introducida por la naturaleza recursiva de la función será ~ n y complejidad debido al bucle for n. La complejidad total será n*n.

Nota: Esta es una forma rápida y sucia de calcular la complejidad (¡nada oficial!). Me encantaría escuchar comentarios sobre esto. Gracias.

Eres capaz de animar nuestra labor fijando un comentario o valorándolo te estamos agradecidos.

---

---

Utiliza Nuestro Buscador