Return to search

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.

Identiferoai:union.ndltd.org:IBICT/oai:lume.ufrgs.br:10183/2133
Date January 2000
CreatorsLoreto, Aline Brum
ContributorsCunha, Rudnei Dias da, Fachin, Maria Paula Goncalves
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0021 seconds