projeto e analise de algoritmos

Rafael Sales 414476
Turma A
Exercícios do Desafio
1) Programação Dinâmica tem a ideia de que dividindo um problema maior em subproblemas, e juntando a solução ótima desses subproblemas, teremos uma solução ótima para o problema maior.
2) Na Programação Dinâmica, os resultados dos subproblemas são armazenados, para que, se existir outro subproblema igual, não seja calculado novamente, apenas resgatado a solução desse subproblema da memória, o que não ocorre na
Divisão e Conquista.
3) A Programação Dinâmica é indicada quando na divisão do problema em subproblemas, pode-se encontrar subproblemas iguais. Assim com a programação Dinâmica não será necessário calcular esses subproblemas novamente. 4) Quando a junção de soluções ótimas locais não garante uma solução ótima global, como no caso do Problemas da Alocação de Sala, visto em aula.
5)
Fibonacci(n){ se n== 2 ou n==1 então retorne 1 senão retorne (Fibonacci(n-1) + Fibonacci(n-2))
}
O((

√

) ), ou seja, exponencial!

fibonacciDinâmico(n){ int i = 1, j = 0, k, m para k de 1 até n faça m=i+j i=j j=m retorne j
}
O (n), ou seja, linear!

6) Busca Sequencial possui O(n), complexidade linear, não sendo necessário o uso de programação dinâmica.
Busca Binária possui O(log n), complexidade logarítmica, não sendo necessário o uso de programação dinâmica.
Selection Sort possui O( ), complexidade exponencial, porém não pode ser aplicado a
Programação Dinâmica, pois o problema não possui uma superposição de subproblemas. Maximum Subarray possui O(n log n) e não precisa ser aplicado a Programação
Dinâmica, pois não existe repetição de subproblemas.
Hire Assistent possui O( ), complexidade linear, não sendo necessária a aplicação da
Programação Dinâmica.