Cálculo da complexidade exata de algoritmos do tipo Divisão-e-Conquista via Maple
Fecha
2001Autor
Resumo
A equação de complexidade de um algoritmo recursivo 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õe-se um esquema de solução de equações de recorrência (lineares e do tipo divisão-e-conquista) resolvidas através do aplicativo matemático Maple, resultando em uma expressão algébrica exata para a complexidade. Desenvolveu-se um procedimento no Maple (bloco de coma ...
A equação de complexidade de um algoritmo recursivo 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õe-se um esquema de solução de equações de recorrência (lineares e do tipo divisão-e-conquista) resolvidas através do aplicativo matemático Maple, resultando em uma expressão algébrica exata para a complexidade. Desenvolveu-se um procedimento no Maple (bloco de comandos) para a solução destas equações de recorrência. O objetivo é obter uma forma geral de calcular a complexidade de um algoritmo desenvolvido pelo método Divisão-e-Conquista utilizando o aplicativo matemático Maple. ...
En
Seleta do XXIII Congresso Nacional de Matemática Aplicada e Computacional. São Carlos. Vol. 2, n. 1 (2001), p. 125-134.TEMA : tendências em matemática aplicada e computacional. São Carlos. Vol. 2, n. 1 (2001), p. 125-134.
Origen
Nacional
Colecciones
-
Artículos de Periódicos (40021)Ciencias Exactas y Naturales (6101)
Este ítem está licenciado en la Creative Commons License