Cálculo da complexidade exata de algoritmos do tipo divisão-e-conquista através das equações características

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.

Author dc:creator

• Loreto, Aline Brum

Advisor dc:contributor.advisor

• Cunha, Rudnei Dias da

• Análise matemática
• Algoritmos recursivos
• Complexidade : Algoritmos

Statement dc:rights

• Open Access

Language dc:language.iso

por

Handle dc:identifier.uri

http://hdl.handle.net/10183/2133

OAI identifier oai:identifier

oai:www.lume.ufrgs.br:10183/2133