Recursión y Big O

Question

He estado trabajando a través de una tarea reciente de informática que involucra recursividad y notación de gran O. Creo que entiendo esto bastante bien (¡sin duda no perfectamente!) Pero hay una pregunta en particular que me está dando más problemas. Lo curioso es que al mirarlo, parece ser el más simple en la tarea.

Proporcione la mejor tasa de crecimiento utilizando la notación grande-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 (log n 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 tomará ese programa o proceso. Siento que esta recursión particular debe ser O (n), ya que, como máximo, la recursión solo se produce una vez para cada valor de n. Como n no está disponible, es mejor que eso, O (nlogn), o peor, son las otras tres opciones.

Entonces, mi pregunta es: ¿Por qué no es esto O (n)?

Answer 1

Hay un par de formas diferentes de resolver 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.

Puede usar los otros dos métodos, pero la forma más fácil para este problema es resolverlo de forma iterativa.

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

Ver 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 estricto es Θ (2 ⁿ).

Answer 2

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 3

Creo que han entendido mal la pregunta un poco. No le pregunta cuánto tiempo llevaría resolver la recurrencia. Se pregunta qué es el gran O (el límite asintótico) de la solución en sí.

Lo que tienes que hacer es crear una solución cerrada, i. mi. la fórmula no recursiva para T (n), y luego determinar cuál es la gran O de esa expresión.

Answer 4

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

No, no es así. Muy por el contrario:

en cuenta que por n iteraciones, tengamos tiempo R en ejecución. Entonces, para n + 1 iteraciones conseguiremos exactamente R + 1.

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

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

Lo que tienes que hacer es encontrar una solución de forma cerrada, i. mi. la fórmula no recursiva para T (n), y luego determinar cuál es la gran O de esa expresión.

Es suficiente para 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 5

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

Dicho de otra manera: la recurrencia produce:

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

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

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

Answer 6

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

En la pregunta real. La solución general puede resolverse obviamente en tiempo constante si no está haciendo la recursión

(T (n) = 2^(n - 1) + 2^(n) - 1), así que eso no es lo que ellos ' preguntando

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

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

Obviamente es O (n).

Por lo tanto, parece ser una pregunta mal formulada, y es probable que le pregunten el crecimiento de la función en sí, no la complejidad del código. Eso es 2^n. Ahora haga el resto de su tarea ... y estudie en O (n * log n)

Answer 7

Es fácil calcular una solución de forma cerrada para la recursión. Por inspección, que supongo que la solución es

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

Entonces demostrar 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 la segunda parte 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 la gente que respondió O (n): No podría estar más de acuerdo con Dima. El problema es no cuando se solicita el límite superior más ajustado 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 requiere el límite superior más estricto en T (n) en sí, y ese es el exponencial.