Recursion y Big O

Question

He estado trabajando a través de una tarea reciente de informática que incluye recursión y gran notación. Creo que entiendo esto bastante bien (aunque ciertamente no perfectamente), pero hay una pregunta en particular que me está causando la mayor cantidad de problemas. Lo extraño es que al mirarlo, parece ser el más sencillo en la tarea.

¿Proporciona la mejor tasa de crecimiento utilizando la notación big-Oh para la solución a la siguiente recurrencia?

T (1) = 2

T (n) = 2T (n - 1) + 1 para n > 1

Y las opciones son:

• O (n log n)
• O (n ^ 2)
• O (2 ^ n)
• O (n ^ n)

Entiendo que la O grande funciona como un límite superior, para describir la mayor cantidad de cálculos, o el tiempo de ejecución más alto, que llevará el programa o proceso. Siento que esta recursión en particular debería ser O (n), ya que, a lo sumo, la recursión solo ocurre una vez para cada valor de n. Dado que n no está disponible, es mejor que eso, O (nlogn), o peor, siendo las otras tres opciones.

Entonces, mi pregunta es: ¿por qué no es esta O (n)?

Answer 1

Hay un par de formas diferentes para resolver las recurrencias: sustitución, árbol de recurrencia y teorema maestro. El teorema maestro no funcionará en el caso, porque no se ajusta a la forma del teorema maestro.

Podrías usar los otros dos métodos, pero la forma más fácil de resolver este problema es resolverlo de manera iterativa.

T (n) = 2T (n-1) + 1
T (n) = 4T (n-2) + 2 + 1
T (n) = 8T (n-3) + 4 + 2 + 1
T (n) = ...

¿Ves el patrón?

T (n) = 2 ^n-1 ·T (1) + 2 ^n-2 + 2 ^n-3 +. .. + 1
T (n) = 2 ^n-1 ·2 + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

Por lo tanto, el límite más estrecho es T (2 ⁿ ).

Answer 2

Creo que has malinterpretado un poco la pregunta. No le pregunta cuánto tiempo tomaría resolver la recurrencia. Es preguntar cuál es la gran O (el límite asintótico) de la solución en sí misma.

Lo que debe hacer es encontrar una solución de formulario cerrado, i. mi. La fórmula no recursiva para T (n), y luego determinar cuál es la O grande de esa expresión.

Answer 3

La pregunta es pedir la notación big-Oh para la solución a la recurrencia, no el costo del cálculo de la recurrencia.

Dicho de otra manera: la recurrencia produce:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

¿Qué notación big-Oh describe mejor la secuencia 2, 5, 11, 23, 47, ...

La forma correcta de resolver eso es resolver las ecuaciones de recurrencia.

Answer 4

Creo que esto será exponencial. Cada incremento en n hace que el valor sea el doble de grande.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T (x) sería el tiempo de ejecución del siguiente programa (por ejemplo):

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 5

  

Creo que esto será exponencial. Cada incremento en n trae el doble de cálculo.

No, no lo hace. Muy por el contrario:

Considere que para las iteraciones n , obtenemos el tiempo de ejecución R . Luego, para n + 1 iteraciones obtendremos exactamente R + 1.

Por lo tanto, la tasa de crecimiento es constante y el tiempo de ejecución general es O ( n ).

Sin embargo, creo que la suposición de Dima sobre la pregunta es correcta, aunque su solución es demasiado complicada:

  

Lo que debe hacer es encontrar una solución de formulario cerrado, i. mi. La fórmula no recursiva para T (n), y luego determinar cuál es la O grande de esa expresión.

Es suficiente examinar el tamaño relativo de T ( n ) y T ( n + 1) iteraciones y determinar la tasa de crecimiento relativo. La cantidad obviamente se duplica, lo que da directamente el crecimiento asintótico.

Answer 6

Primero que nada, las cuatro respuestas son peores que O (n) ... O (n * log n) es más complejo que el simple O (n). Lo que es más grande: 8 u 8 * 3, 16 o 16 * 4, etc ...

A la pregunta real. La solución general, obviamente, se puede resolver en un tiempo constante si no está haciendo recursión

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1), así que eso no es lo que están preguntando.

Y como puede ver, si escribimos el código recursivo:

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

Obviamente es O (n).

Entonces, parece ser una pregunta mal formulada, y probablemente te estén preguntando el crecimiento de la función en sí, no la complejidad del código. Eso es 2 ^ n. Ahora, haz el resto de tu tarea ... y estudia en O (n * log n)

Answer 7

Calcular una solución de forma cerrada para la recursión es fácil. Por inspección, supones que la solución es

T(n) = 3*2^(n-1) - 1

Luego, demuestras por inducción que esto es de hecho una solución. Caso base:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

Inducción:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

donde la primera igualdad se deriva de la definición de recurrencia, y el segundo de la hipótesis inductiva. QED.

3 * 2 ^ (n-1) - 1 es claramente Theta (2 ^ n), por lo tanto, la respuesta correcta es la tercera.

A las personas que respondieron O (n): No podría estar más de acuerdo con Dima. El problema no solicita el límite superior más estrecho a la complejidad computacional de un algoritmo para calcular T (n) (que ahora sería O (1), ya que se ha proporcionado su forma cerrada). El problema solicita el límite superior más ajustado en T (n) en sí mismo , y ese es el exponencial.