in

Guía para principiantes de programación dinámica

0UisuFLtOG0CLJk39
(Foto de Chris Ried en Unsplash)

TUTORIAL DE PROGRAMACIÓN

Guía para principiantes de programación dinámica

Optimice su código usando algunas técnicas simples

Shantnu y Kartik

Shantnu y Kartik

4 de agosto de 2020·7 min de lectura

La programación dinámica es un arte, cuantos más problemas resuelvas, más fácil se vuelve.

A veces, cuando escribe código, puede llevar algún tiempo ejecutarlo o puede que nunca se ejecute, incluso si su lógica está bien. Se me ocurrió el mismo problema al resolver las preguntas de desafío de Google Foobar y me di cuenta de que la solución no estaba optimizada y estaba usando toda la RAM disponible (para valores grandes).

Se requiere un enfoque completamente diferente para resolver este tipo de problemas, es decir, «optimización de código» siguiendo el concepto de programación dinámica.

¿Qué es la programación dinámica?

La programación dinámica es un excelente enfoque que se puede aplicar a una clase de problemas para obtener una solución eficiente y óptima.

En En palabras simples, el concepto detrás de la programación dinámica es dividir los problemas en subproblemas y guardar el resultado para el futuro para que no tengamos que volver a calcular el mismo problema. Una mayor optimización de los subproblemas que optimiza la solución global se conoce como propiedad de subestructura óptima.

Dos formas de aplicar la programación dinámica:

De arriba hacia abajo:

En este método, el problema se desglosa y si el problema ya está resuelto, se devuelve el valor guardado; de lo contrario, se memoriza el valor de la función, es decir, se calculará por primera vez; en cualquier otro momento, se volverá a llamar el valor almacenado. Memorización es una excelente forma para programas computacionalmente costosos. No confunda la memorización con memorizar.

Memoize! = Memorizar

De abajo hacia arriba:

Esta es una forma eficaz de evitar la recursividad al disminuir la complejidad de tiempo que genera la recursividad (es decir, el costo de memoria debido al recálculo de los mismos valores). Aquí, se calculan las soluciones a pequeños problemas que construyen la solución al problema general. (Tendrá más claridad sobre esto con los ejemplos que se explican más adelante en el artículo).

Entender dónde usar esta técnica

Como se mencionó anteriormente, si observa que el problema se puede dividir en subproblemas y estos se pueden dividir en otros mucho más pequeños y algunos de ellos se superponen (es decir, requiere el cálculo de valores calculados previamente). El objetivo principal es optimizar el código reduciendo la repetición de valores almacenando los resultados de los subproblemas.

La programación dinámica se puede aplicar a cualquier problema de este tipo que requiera volver a calcular ciertos valores para llegar a la solución final.

Programación dinámica y recursiva

Recuerde, la programación dinámica no debe confundirse con la recursividad.

Recursividad es una forma de encontrar la solución expresando el valor de una función en términos de otros valores de esa función directa o indirectamente y dicha función se llama función recursiva. Sigue un enfoque de arriba hacia abajo.

Programación dinámica no es más que recursividad con memorización, es decir, calcular y almacenar valores a los que se puede acceder más tarde para resolver subproblemas que ocurren nuevamente, lo que hace que su código sea más rápido y reduce la complejidad del tiempo (se reducen los ciclos de CPU de cómputo).

Aquí, la idea básica es ahorrar tiempo mediante un uso eficiente del espacio. La recursividad lleva tiempo pero no espacio, mientras que la programación dinámica usa espacio para almacenar soluciones a subproblemas para referencia futura, lo que ahorra tiempo.

Comprensión de la programación dinámica con ejemplos

Comencemos con un ejemplo básico de la serie Fibonacci.

Serie de Fibonacci es una secuencia de números de tal manera que cada número es la suma de los dos anteriores, comenzando por 0 y 1.

F (n) = F (n-1) + F (n-2)

  • Método recursivo:
def r_fibo(n):
if n <= 1:
return n
else:
return(r_fibo(n-1) + r_fibo(n-2))

Aquí, el programa se llamará a sí mismo, una y otra vez, para calcular más valores. El cálculo de la complejidad temporal del enfoque basado en la recursividad es de alrededor de O (2 ^ N). La complejidad espacial de este enfoque es O (N) ya que la recursividad puede llegar al máximo a N.

Por ejemplo-

F (4) = F (3) + F (2) = ((F (2) + F (1)) + F (2) = ((F (1) + F (0)) + F (1) ) + (F (1) + F (0))

En este método, los valores como F (2) se calculan dos veces y las llamadas para F (1) y F (0) se realizan varias veces. Imagina el número de repeticiones si tienes que calcularlo F (100). Este método es ineficaz para valores grandes.

  • Método de arriba hacia abajo
def fibo(n, memo):
if memo[n] != null:
return memo[n]
if n <= 1:
return n
else:
res = fibo(n-1) + fibo(n+1)
memo[n] = res
return res

Aquí, el tiempo de cálculo se reduce significativamente ya que las salidas producidas después de cada recursión se almacenan en una lista que se puede reutilizar más tarde. Este método es mucho más eficaz que el anterior.

  • De abajo hacia abajo
def fib(n):
if n<=1:
return n
list_ = [0]*(n+1)
list_[0] = 0
list_[1] = 1
for i in range(2, n+1):
list_[i] = list_[i-1] + list[i-2]
return list_[n]

Este código no usa recursividad en absoluto. Aquí, creamos una lista vacía de longitud (n + 1) y establecemos el caso base de F (0) y F (1) en las posiciones de índice 0 y 1. Esta lista se crea para almacenar los valores calculados correspondientes usando un bucle for para valores de índice 2 hasta n.

A diferencia del método recursivo, la complejidad temporal de este código es lineal y lleva mucho menos tiempo calcular la solución, ya que el ciclo va de 2 an, es decir, se ejecuta en O(norte). Este enfoque es el forma más eficiente escribir un programa.

Complejidad de tiempo: O (n)

Ahora, veamos otro ejemplo (este es un problema de nivel intermedio):

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

XPksLEGk2urdd73QnTSmeX 1200 80

El mejor procesador de texto gratuito 2021: alternativas a Microsoft Word

social og hcm

Software de nómina | oracleHCM