📊 Análise de Complexidade Computacional do Algoritmo Ingênuo

Análise teórica e empírica da complexidade do algoritmo de ordenação insertion sort para encontrar o n-ésimo menor elemento

📋 Sobre o Projeto

Este repositório contém uma análise completa da complexidade computacional do algoritmo ingênuo baseado no insertion sort para encontrar o k-ésimo menor elemento em uma lista. A abordagem combina fundamentos teóricos com validação empírica através de experimentos controlados.

🎯 Objetivos

• 📚 Análise Teórica: Demonstrar matematicamente a complexidade do algoritmo
• 🔬 Validação Empírica: Corroborar os resultados teóricos com dados experimentais
• 📈 Visualização: Apresentar os resultados de forma clara e intuitiva
• 🧪 Reprodutibilidade: Fornecer código para replicação dos experimentos

---

🔍 Metodologia

📚 Análise Teórica

Análise detalhada da complexidade assintótica do algoritmo:

Componente	Complexidade	Justificativa
Insertion Sort	O(n²)	Duas iterações aninhadas sobre a lista
K-th Smallest	O(n²)	Utiliza insertion sort como sub-rotina
Caso Médio	Θ(n²)	Comportamento quadrático mantido
Melhor Caso	Ω(n)	Lista já ordenada (raro na prática)

🧪 Análise Empírica

Experimentos controlados para validação prática:

• 📏 Variação de Tamanho: Listas de 100 a 10.000 elementos
• ⏱️ Medição de Tempo: Execuções repetidas para precisão estatística
• 📊 Análise Comparativa: Tempo máximo vs tempo médio de execução
• 🎯 Validação: Correlação entre crescimento teórico e empírico

---

🛠️ Implementação

💻 Algoritmo Principal

def insertion_sort_kth(arr, k):
    """
    Encontra o k-ésimo menor elemento usando insertion sort
    Complexidade: O(n²) no pior caso
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr[k - 1]

📈 Métricas de Avaliação

Métrica	Descrição	Fórmula/Abordagem
Tempo de Execução	Tempo real de processamento	time.perf_counter()
Complexidade Temporal	Crescimento em função de n	Análise assintótica
Overhead Experimental	Tempo de medição	Múltiplas execuções

---

📊 Resultados e Conclusões

🎯 Principais Descobertas

1. ✅ Confirmação Empírica: Dados experimentais validam a complexidade O(n²)
2. 📈 Crescimento Quadrático: Tempo de execução cresce proporcional a n²
3. 🎪 Consistência: Comportamento previsível across diferentes cenários
4. 📉 Limitações Práticas: Algoritmo inviável para grandes volumes de dados

👥 Equipe de Pesquisa

🔬 Pesquisadores Responsáveis

Thomaz R. Lima 🎯 Análise Teórica 📊 Experimentação

André Fonseca 💻 Implementação 📈 Visualização

---

📚 Referências

1. Cormen, T. H., et al. "Introduction to Algorithms"
2. Knuth, D. E. "The Art of Computer Programming"
3. Sedgewick, R., & Wayne, K. "Algorithms"