ESTRUTURAS DE DADOS RETROATIVAS: UM MAPEAMENTO SISTEMÁTICO

Resumo

Face à miniaturização dos aparelhos eletrônicos e devido àquantidade de dados processados por eles, as aplicaçõesdesenvolvidas necessitam ser eficientes em termos de consumo dememória e complexidade temporal. Estruturas de dadosretroativas são estruturas em que é possível realizar umamodificação no passado e observar o efeito dessa modificação emsua linha temporal. Essas estruturas são utilizadas em algunsproblemas geométricos e em outros relacionados a grafos, como oproblema do caminho mínimo em grafos dinâmicos. Contudo, aimplementação dessas estruturas de maneira otimizada nemsempre é trivial. Diante desse cenário, este trabalho apresenta osresultados de uma pesquisa relacionada a estruturas de dadosretroativas, visando comparar o desempenho das implementaçõespropostas por variados autores em relação às implementaçõestriviais dessas estruturas. O método de pesquisa adotado foi oestudo dos artigos relacionados às estruturas de dados retroativas,a partir de um mapeamento sistemático, e a análise dedesempenho dessas estruturas codificadas na linguagem C++. Asestruturas identificadas nesse mapeamento apresentaram melhoresresultados no que tange ao consumo de espaço e tempo deprocessamento com relação às suas implementações por forçabruta, porém, em alguns casos, com constantes altas.