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

267

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);
}
Michael_19
fuente
44
Si no desea pasar por el análisis cada vez, existe una técnica de recuadro negro llamada método Master. Pero con el supuesto de que todas las divisiones recursivas de entradas son del mismo tamaño en cada caso.
Vivek Krishna

Respuestas:

345

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;)

descifrador
fuente
a la derecha sobre el quinto, la n disminuirá para el bucle for pero para el cuarto no creo que sea n ^ 2 porque es como un árbol cada vez que llamas la recursión dos veces, por lo que debería ser 2 ^ n más ese fue tu responde en el comentario anterior.
codificador
2
@MJGwater Deje que el tiempo de ejecución del bucle sea m. Cuando la ejecución recursiva 1 vez, toma m ejecutar el ciclo. Cuando el recursivo se ejecuta 2 veces, el ciclo también se ejecuta 2 veces, por lo que tarda 2m ... y así sucesivamente. Entonces es '*', no '^'.
bjc
3
@coder La explicación para 5 parece extraña. Si incrementar en 2 resulta en n/2iteraciones del forciclo, ¿por qué disminuir en 5 no daría lugar a n/5llamadas recursivas? Esto aún resultaría O(n^2)pero parece una explicación más intuitiva. ¿Por qué mezclar resta y división cuando son esenciales para hacer lo mismo?
Jack
1
@coder, entonces para el # 4, si hubiera 3 llamadas recursivas en la definición de la función, ¿tendría una complejidad de tiempo de O (3 ^ n)? Y para 5 llamadas recursivas sería O (5 ^ n), ¿correcto?
rmutalik
1
@ Jack Sí, también me preguntaba lo mismo. Debe ser n/5no n-5. Y finalmente, todo se reducirá a O(N^2).
Anuj
128

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)
nhahtdh
fuente
1
Recientemente fallé una pregunta de la entrevista (y al extender la entrevista) que tiene que ver con el análisis de la complejidad de tiempo y espacio de una función recursiva de Fibonacci. Esta respuesta es épica y ayudó mucho, me encanta, desearía poder votarte dos veces. Sé que es viejo, pero ¿tiene algo similar para calcular el espacio, tal vez un enlace, algo?
Dimitar Dimitrov
Para el número 4, aunque el resultado sea el mismo, ¿no debería ser la inducción la siguiente? T (n) = a + 2T (n-1) = a + 2a + 4T (n-1) = 3a + 4a + 8T (n-1) = a * (2 ^ n - 1) + 2 ^ n * T (0) = a * (2 ^ n - 1) + b * 2 ^ n = (a + b) * 2 ^ n - a = O (2 ^ n)
Snowfish
27

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.

Shubham
fuente
Excelente respuesta! Tengo una pregunta sobre la cuarta función. Si hubiera tenido tres llamadas recursivas, la respuesta sería (3 ^ n). ¿O simplemente dirías (2 ^ n)?
Ben Forsrup
@Shubham: # 4 no me parece correcto. Si el número de hojas es, 2^nentonces la altura del árbol debe ser n, no log n. La altura solo sería log nsi se nrepresenta el número total de nodos en el árbol. Pero no lo hace.
Julian A.
@BenForsrup: será 3 ^ n porque cada nodo tendrá tres nodos secundarios. La mejor manera de estar seguros de esto es dibujar el árbol recursivo con valores ficticios.
Shubham
# 2 debería ser n-5 no n / 5
Fintasys
7

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 :)

OhadM
fuente
1

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
  1. 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
  1. 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)
  1. 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
  1. 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
higlu
fuente