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

Mañana tengo un examen intermedio de informática y necesito ayuda para determinar la complejidad de estas funciones recursivas. Sé cómo resolver casos simples, pero todavía estoy tratando de aprender cómo 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);
}

La complejidad del 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 O(n), por lo que a menudo se llama 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 lo es O(n). (Realmente 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 dividimos entre 5 antes de llamar a la función, por lo que su O(log(n))(base 5), a menudo llamada logarítmica y, con mayor frecuencia, la anotación Big O y el análisis de complejidad usan la base 2.
4. En el cuarto, es O(2^n), o exponencial , ya que cada llamada de función se llama a sí misma dos veces a menos que se haya repetido n veces.

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

   Buena suerte en tus exámenes parciales;)

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

Consideraremos el caso n >= 0en la parte a continuación.

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 algo constante

Por inducción:

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

donde a, b son algunas constantes y k <= 0

3)

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

donde a es algo 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 algo 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 alguna constante

Reescribe n = 5q + rdonde 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) / 5, y desde r <5, podemos considerarlo una constante, por lo queq = 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 para 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 recursividad. Una vez que tengas el árbol recursivo:

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

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

2. La segunda función tendrá la longitud n/5y el número de nodos hoja nuevamente, 1por lo que la complejidad será n/5 * 1 = n/5. Debe ser aproximado an

3. Para la tercera función, dado que nse 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, ya que cada nodo tendrá dos nodos secundarios, el número de nodos hoja será igual (2^n)y la longitud del árbol recursivo será ntan compleja (2^n) * n. Pero como nes insignificante frente a (2^n)esto, puede ser ignorado y solo se puede decir que la complejidad lo 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 el forbucle en cada función. Haciendo el cálculo anterior, la complejidad introducida por la naturaleza recursiva de la función será ~ ny la complejidad debida al bucle for n. Complejidad total será n*n.

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

Podemos demostrarlo matemáticamente, que es algo que me faltaba en las respuestas anteriores.

Puede ayudarte dramáticamente a entender cómo calcular cualquier método. Recomiendo leerlo de arriba a abajo para comprender completamente cómo hacerlo:

1. T(n) = T(n-1) + 1Significa que el tiempo que tarda el método en finalizar es igual al mismo método pero con n-1, que es T(n-1)y ahora agregamos + 1porque es el tiempo que lleva completar las operaciones generales (excepto T(n-1)). Ahora, vamos a encontrar T(n-1)la siguiente manera: T(n-1) = T(n-1-1) + 1. Parece que ahora podemos formar una función que nos puede dar algún tipo de repetición para que podamos entender completamente. Colocaremos el lado derecho del T(n-1) = ...lugar de T(n-1)dentro del método T(n) = ...que nos dará: T(n) = T(n-1-1) + 1 + 1que es T(n) = T(n-2) + 2o, en otras palabras, tenemos que encontrar nuestra falta k: T(n) = T(n-k) + k. El siguiente paso es tomar n-ky afirmar que n-k = 1porque al final de la recursión tomará exactamente O (1) cuandon<=0. De esta ecuación simple ahora lo sabemos k = n - 1. Coloquemos ken nuestro método final: T(n) = T(n-k) + kque nos dará: T(n) = 1 + n - 1cuál es exactamente no O(n).
2. Es lo mismo que 1. Puede probarlo usted mismo y ver que lo obtiene O(n).
3. T(n) = T(n/5) + 1como antes, el tiempo para que este método termine es igual al tiempo del mismo método, pero con el n/5cual está limitado T(n/5). Encontremos T(n/5)como en 1: T(n/5) = T(n/5/5) + 1que es T(n/5) = T(n/5^2) + 1. Vamos a cabo T(n/5)en el interior T(n)para el cálculo final: T(n) = T(n/5^k) + k. De nuevo como antes, n/5^k = 1que es n = 5^kexactamente como preguntar qué en potencia de 5 nos dará n, la respuesta es log5n = k(log de base 5). Coloquemos nuestros hallazgos de la T(n) = T(n/5^k) + ksiguiente manera: T(n) = 1 + lognque esO(logn)
4. T(n) = 2T(n-1) + 1lo que tenemos aquí es básicamente lo mismo que antes, pero esta vez estamos invocando el método recursivamente 2 veces, por lo que lo multiplicamos por 2. Veamos T(n-1) = 2T(n-1-1) + 1cuál es T(n-1) = 2T(n-2) + 1. Nuestro próximo lugar como antes, ubiquemos nuestro hallazgo: T(n) = 2(2T(n-2)) + 1 + 1que es lo T(n) = 2^2T(n-2) + 2que nos da T(n) = 2^kT(n-k) + k. Encontremos kreclamando lo que n-k = 1es k = n - 1. Coloquemos de la ksiguiente manera: T(n) = 2^(n-1) + n - 1que es aproximadamenteO(2^n)
5. T(n) = T(n-5) + n + 1Es casi lo mismo que 4 pero ahora agregamos nporque tenemos un forbucle. Veamos T(n-5) = T(n-5-5) + n + 1cuál es T(n-5) = T(n - 2*5) + n + 1. Vamos a colocarlo: T(n) = T(n-2*5) + n + n + 1 + 1)cuál es T(n) = T(n-2*5) + 2n + 2)y para k: T(n) = T(n-k*5) + kn + k)nuevamente: n-5k = 1cuál es n = 5k + 1eso es más o menos n = k. Esto nos dará: T(n) = T(0) + n^2 + nque es más o menos O(n^2).

Ahora recomiendo leer el resto de las respuestas, que ahora le darán una mejor perspectiva. Buena suerte ganando esas grandes O :)

La clave aquí es visualizar el árbol de llamadas. Una vez hecho eso, la complejidad es:

nodes of the call tree * complexity of other code in the function

El último término se puede calcular de la misma manera que lo hacemos para una función iterativa normal.

En cambio, los nodos totales de un árbol completo se calculan como

                  C^L - 1
                  -------  , when C>1
               /   C - 1
              /
 # of nodes =
              \    
               \ 
                  L        , when C=1

Donde C es el número de hijos de cada nodo y L es el número de niveles del árbol (raíz incluida).

Es fácil visualizar el árbol. Comience desde la primera llamada (nodo raíz) y luego dibuje un número de hijos igual al número de llamadas recursivas en la función. También es útil escribir el parámetro pasado a la sub-llamada como "valor del nodo".

Entonces, en los ejemplos anteriores:

1. el árbol de llamadas aquí es C = 1, L = n + 1. La complejidad del resto de la función es O (1). Por lo tanto, la complejidad total es L * O (1) = (n + 1) * O (1) = O (n)

n     level 1
n-1   level 2
n-2   level 3
n-3   level 4
... ~ n levels -> L = n

2. El árbol de llamadas aquí es C = 1, L = n / 5. La complejidad del resto de la función es O (1). Por lo tanto, la complejidad total es L * O (1) = (n / 5) * O (1) = O (n)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

3. El árbol de llamadas aquí es C = 1, L = log (n). La complejidad del resto de la función es O (1). Por lo tanto, la complejidad total es L * O (1) = log5 (n) * O (1) = O (log (n))

n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)

4. El árbol de llamadas aquí es C = 2, L = n. La complejidad del resto de la función es O (1). Esta vez usamos la fórmula completa para el número de nodos en el árbol de llamadas porque C> 1. Por lo tanto, la complejidad total es (C ^ L-1) / (C-1) * O (1) = (2 ^ n - 1 ) * O (1) = O (2 ^ n) .

               n                   level 1
      n-1             n-1          level 2
  n-2     n-2     n-2     n-2      ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3    ...     
              ...                ~ n levels -> L = n

5. El árbol de llamadas aquí es C = 1, L = n / 5. La complejidad del resto de la función es O (n). Por lo tanto, la complejidad total es L * O (1) = (n / 5) * O (n) = O (n ^ 2)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5