recursion - recursivos - ejemplo algoritmo complejidad exponencial

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

Question

Tengo un término medio de informática mañana y necesito ayuda para determinar la complejidad de estas funciones recursivas. Sé cómo resolver casos simples, pero todavía estoy tratando de aprender a resolver estos casos más difíciles. Estos fueron solo algunos de los problemas de ejemplo que no pude resolver. Cualquier ayuda sería muy apreciada y sería de gran ayuda en mis estudios. ¡Gracias!

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

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

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

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d/n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

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

Answer 1

La complejidad de tiempo, en notación Big O, para cada función, está en orden numérico:

1. La primera función se llama recursivamente n veces antes de llegar al caso base, por lo que es O(n) , a menudo llamada lineal .
2. La segunda 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)).
3. Esta función es log (n) base 5, por cada vez que lo dividimos por 5 antes de llamar a la función, su O(log(n)) (base 5), a menudo llamada logarítmica y más a menudo Big O, y el análisis de complejidad usa base 2 .
4. En el cuarto, es O(2^n) , o exponencial , ya que cada llamada a función se llama a sí misma dos veces a menos que haya sido recursada n veces.

5. En cuanto a la última función, el ciclo for toma n / 2 ya que estamos aumentando en 2, y la recurrencia toma n-5 y dado que el ciclo for se llama recursivamente, por lo tanto, la complejidad temporal está en (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2-10n, debido al comportamiento asintótico y al peor de los casos, o al límite superior que busca la gran O, solo estamos interesados ​​en el término más grande, por lo que O(n^2) .

   Buena suerte en tus midterms;)

Answer 2

Para el caso donde n <= 0 , T(n) = O(1) . Por lo tanto, la complejidad del tiempo dependerá de cuando n >= 0 .

Consideraremos el caso n >= 0 en la parte siguiente.

1.

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

donde a es algo 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 yk <= 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 * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

donde a, b son algunas constantes.

5.

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

Podemos probar por inducción que T(5k) >= T(5k - d) donde d = 0, 1, 2, 3, 4

Escriba n = 5m - b (m, b son enteros; b = 0, 1, 2, 3, 4), luego m = (n + b) / 5 :

T(n) = T(5m - b) <= T(5m)

(En realidad, para ser más riguroso aquí, se debe definir una nueva función T''(n) tal que T''(5r - q) = T(5r) donde q = 0, 1, 2, 3, 4 Sabemos T(n) <= T''(n) como se demostró anteriormente. Cuando sabemos que T''(n) está en O(f) , lo que significa que existen constantes a, b de modo que T''(n) <= a * f(n) + b , podemos derivar que T(n) <= a * f(n) + b y por lo tanto T(n) está en O(f) . Este paso no es realmente necesario, pero es más fácil pensar cuando no tienes que lidiar con el resto).

Expansión T(5m) :

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

Por lo tanto, T(n) es O(n ^ 2) .

Answer 3

Una de las mejores maneras que encuentro para aproximar la complejidad del algoritmo recursivo es dibujando el árbol de recursión. Una vez que tienes 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 un número de nodo de hoja 1 por lo que la complejidad será n*1 = n

2. La segunda función tendrá la longitud de n/5 y la cantidad de nodos de hojas nuevamente 1 por lo que la complejidad será n/5 * 1 = n/5 . Debe ser aproximado a n

3. Para la tercera función, dado 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 como n es insignificante delante de (2^n) , puede ignorarse y solo puede decirse 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 loop en cada función. Al hacer el cálculo anterior, la complejidad introducida por la naturaleza recursiva de la función será ~ n complejidad debido a for loop n . La complejidad total será n*n .

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