Aula 04 - Complexidade de Algoritmo
Fibonacci com Programação Dinâmica
Reduzindo a complexidade da função fibonacci recursiva para O(n).
Será utilizada a técnica de programação dinâmica.
Se gostarem do conteúdo dêem um joinha 👍 na página do Código Fluente no
Facebook
Esse é o link do código fluente no Pinterest
Meus links de afiliados:
Programação Dinâmica
Seu criador
Richard Bellman explica o raciocínio por trás do termo programação dinâmica em sua autobiografia,
Eye of the Hurricane: Uma Autobiografia (1984).
Ele explica que trabalhava na RAND (research and development) nos anos 50.
O secretário de defesa na época era
Charles Erwin Wilson, e ele não gostava do termo pesquisa, na sua autobiografia ele diz:
"ele tinha um medo patológico e ódio da palavra pesquisa, não estou usando o termo de ânimo leve, eu estou usando isso precisamente, o rosto se encheria, ele ficaria vermelho, e ele ficaria violento se as pessoas usassem o termo pesquisa em sua presença."
Por isso ele diz também: "Os anos 50 não foram bons anos para matemática".
A primeira tarefa de
Bellman foi encontrar um nome para processos de decisão em múltiplos estágios, que soassem bem aos ouvidos de
Wilson.
Pensou em várias palavras e acabou chegando ao termo programação dinâmica, pois achou que o termo
dinâmico tem uma propriedade muito interessante como um adjetivo, e é impossível usar a palavra dinâmica em um sentido pejorativo.
Aplicando a técnica
Aplicaremos a técnica de programação dinâmica para reduzir a complexidade da função de fibonacci recursiva de
O(2^n), para
O(n).
Programação dinâmica
Programação dinâmica é um método de construção de algoritmos, geralmente para solução de problemas computacionais de otimização combinatória.
A
programação dinâmica é principalmente uma otimização sobre a recursão simples.
Onde quer que vejamos uma solução recursiva que tenha chamadas repetidas para as mesmas entradas, podemos otimizá-la usando a
Programação Dinâmica.
A ideia é simplesmente armazenar os resultados dos subproblemas, para que não tenhamos que recalculá-los quando for necessário posteriormente.
Essa otimização simples reduz as complexidades de tempo de exponencial para polinomial.
É isso que vamos fazer agora.
Veja no grafo abaixo que a função de fibonacci recursiva simples, que vimo aula passada, faz recálculos desnecessários.
Ela sabe que o fib(0) é 0(zero) e que fib(1) é 1, não precisa calcular, o fib(2) ela vai calcular somando 0(n - 2) com 1 (n - 1), então fib(2) é 1, só que ela faz isso 3 vezes, mas bastava fazer uma vez e memorizar que fib(2) é 1.
A mesma coisa acontece com fib(3), que é calculado duas vezes.
Com a programação dinâmica aplicada a esse caso, evitaremos esses recálculos desnecessários.
O código a seguir é exatamente o mesmo da aula passada, mas, coloquei algumas instruções a mais(em
azul), apenas para medir o tempo de execução do código e comparar as duas implementações:
Fibonnaci com complexidade de
O(2^n) (código da aula passada):
import time
#Recursiva, complexidade O(2^n)
def fib(n):
if n <= 1:
return n
else:
return fib(n - 1) + fib(n - 2)
def main():
n = int(input())
t0= time.process_time()
print( fib(n) )
t1 = time.process_time() - t0
print("Time elapsed: ",abs(t1 - t0))
if __name__ == "__main__":
main()
O arquivo texto de input(
input.txt) tem o número
36, que nosso algoritmo deve dá como resposta
14930352.
Vamos medir a execução e ver quanto tempo ele gasta.
Saída:
14930352
Time elapsed: 8.15625
Agora a implementação da
Fibonnaci recursiva, com programação dinâmica, onde os resultados das computações são guardados, para evitar recálculos:
Fibonnaci com complexidade de
O(n) (código dessa aula):
import time
#Recursiva, complexidade O(n) com memorização (programação dinâmica)
def fib(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
return computed[n]
def main():
n = int(input())
t0= time.process_time()
print( fib(n) )
t1 = time.process_time() - t0
print("Time elapsed: ",abs(t1 - t0))
if __name__ == "__main__":
main()
Saída:
14930352
Time elapsed: 0.03125
Ficamos por aqui, até mais. :)
Se gostarem do conteúdo dêem um joinha 👍 na página do Código Fluente no
Facebook
Esse é o link do código fluente no Pinterest
Meus links de afiliados:
Meu github:
Obrigado, até a próxima e bons estudos. ;)
