Potenciação Divide and Conquer

Método Método Divide and Conquer Divide and Conquer para o para o problema de Potência problema de Potência

Alunos: Adilmar Coelho Dantas

Sara Luzia de Melo

PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃOUniversidade Federal de Uberlândia – UFU

Faculdade de Computação – FACOM

IntroduçãoIntroduçãoProblema

- Dado um número inteiro n e um inteiro x não negativo,

desenvolver um algoritmo que retorne o valor da potência.

Solução Proposta Método Iterativo

Método Recursivo

Método Divide and Conquer

Função pow

Método IterativoMétodo Iterativo

Tempo de Execução:

Custo Linear!!!

Método Método Divide and ConquerDivide and Conquer

Figura 1: Exemplo da divisão de problemas

Método Método Divide and ConquerDivide and Conquer

5 multiplicações

Método Método Divide and ConquerDivide and Conquer

RecorrênciasRecorrências

Funções de Recorrências

Se par

Se ímpar

Custo do algoritmo:

Tempo do algoritmo Tempo do algoritmo divide and conquerdivide and conquer

Implementação e TestesImplementação e Testes

Vamos testar as duas implementações?!

Foi observado que o tempo do algoritmo divide and conquer foi superior ao tempo do algoritmo iterativo para com n relativamente pequeno. - Isto ocorre ao fato de nem todos os subproblemas

gerados serem utilizados na operação.

Quando o valor de entrada “cresce”, o tempo de execução do algoritmo divide and conquer diminui comparado ao linear.

Concluimos que, o método divide and conquer para esse problema de potência é eficiente quando os valores de entrada são “grandes”.

Considerações FinaisConsiderações Finais

Considerações FinaisConsiderações Finais

Considerações FinaisConsiderações Finais

Neste dois casos podemos perceber claramente a eficiência da técnica, quando aplicada para expoentes relativamente maiores.

ReferênciasReferências• Cormen, T. H., Leiserson, C. E., Rivest, R. L.,

and Stein, C. (2002). Algoritmos, Teoria e Prática (2. ed.). MIT Press.