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

Documentos 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