recursion - metodos - recursividad estructura de datos ejemplos

Recursión y gran O (7)

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

No, no es así. Todo lo contrario:

Considere que para n iteraciones, obtenemos 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 de hecho 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 tienes que hacer es crear una solución de forma cerrada, es decir, la fórmula no recursiva para T (n), y luego determinar cuál es la gran O de esa expresión.

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

He estado trabajando a través de una tarea reciente de Informática con 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 usando 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 (n log n)
O (n ^ 2)
O (2 ^ n)
O (n ^ n)

Entiendo que el gran O 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 este O (n)?

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)

Creo que has malinterpretado 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 de forma cerrada, es decir, la fórmula no recursiva para T (n), y luego determinar cuál es la gran O de esa expresión.

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, obviamente, se puede resolver en tiempo constante si no estás haciendo recursividad

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1), entonces 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).

Por lo tanto, parece ser una pregunta mal redactada, 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 ve a hacer el resto de tu tarea ... y estudia en O (n * log n)

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é notación de Big-Oh describe mejor la secuencia 2, 5, 11, 23, 47, ...

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

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

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

Luego, por inducción, demuestras que, de hecho, esta es 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 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 no exige el límite superior más estricto de 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í mismo , y ese es el exponencial.

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 ⁿ ).