Cálculo da complexidade exata de algoritmos do tipo divisão-e-conquista através das equações características
AUTOR(ES)
Loreto, Aline Brum
DATA DE PUBLICAÇÃO
2007
RESUMO
A equação de complexidade de um algoritmo pode ser expressa em termos de uma equação de recorrência. A partir destas equações obtém-se uma expressão assintótica para a complexidade, provada por indução. Neste trabalho, propõem-se um esquema de solução de equações de recorrência usando equações características que são resolvidas através de um "software" de computação simbólica, resultando em uma expressão algébrica exata para a complexidade. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista.
ASSUNTO(S)
análise matemática complexidade : algoritmos recursivos : equações características
ACESSO AO ARTIGO
http://hdl.handle.net/10183/2133Documentos Relacionados
- O método de divisão-e-conquista na solução de auto-sistemas de matrizes simétricas
- Escalonamento Work-Stealing de programas Divisão-e-Conquista com MPI-2
- Sistematização do cálculo das funções do grupo de renormalização através da regularização implícita
- Solução computacional do problema da cavidade cúbica através das equações de Navier-Stokes tridimensionais
- Equações e programa computacional para cálculo do transporte de solutos do solo