Análise de complexidade de algoritmos utilizando métodos empíricos/experimentais

Abstract

A análise de complexidade de algoritmos é fundamental para o desenvolvimento de sistemas de alta performance, permitindo prever o consumo de recursos computacionais. No entanto, a análise assintótica teórica nem sempre reflete o desempenho prático devido a fatores como constantes ocultas, arquitetura de hardware e otimizações de compiladores. Este trabalho propõe uma metodologia automatizada para a análise empírica da complexidade temporal de algoritmos de ordenação, tratando-os como caixas-pretas. O sistema desenvolvido avalia oito algoritmos clássicos (Bubble, Insertion, Merge, Quick, Heap, Counting, Radix e Bucket Sort) em cenários com dados aleatórios, ordenados e reversos. A metodologia reside na aplicação do otimizador Adam (Gradiente Descendente Adaptativo) para ajustar modelos matemáticos (O(n), O(n2) e O(n log n)) aos tempos de execução coletados, utilizando o Erro Quadrático Médio (RMSE) como critério de seleção. Os resultados experimentais confirmaram a hierarquia teórica esperada, validaram casos especiais como o desempenho linear do Insertion Sort em vetores ordenados e evidenciaram a alta instabilidade do Bubble Sort. O estudo conclui que a técnica de ajuste iterativo de curvas é eficaz para classificar algoritmos empiricamente, oferecendo uma ferramenta prática para tomada de decisão em engenharia de software.