Implementação do Algoritmo de Seleção Máximo-Mínimo

Este repositório apresenta uma implementação do algoritmo de seleção simultânea dos valores mínimo e máximo de uma lista, utilizando a estratégia de divisão e conquista.

Visão Geral do Projeto

O algoritmo MaxMin Select tem como objetivo identificar, de maneira eficiente, os menores e maiores elementos de uma sequência, reduzindo a quantidade de comparações necessárias quando comparado a métodos mais simples.

Estratégia do Algoritmo

A lógica do algoritmo está contida no arquivo main.py:

def max_min_select(arr, start, end):
    """
    Determina os valores mínimo e máximo de um array utilizando 
    recursão com base na técnica de divisão e conquista.
    
    Parâmetros:
        arr: Lista de elementos numéricos
        start: Posição inicial do subarray
        end: Posição final do subarray
    
    Retorna:
        Uma tupla (min, max) com os valores encontrados
    """
    # Caso com apenas um elemento
    if start == end:
        return (arr[start], arr[start])
    
    # Caso com dois elementos
    if end == start + 1:
        return (arr[start], arr[end]) if arr[start] < arr[end] else (arr[end], arr[start])
    
    # Encontrar o ponto médio para dividir o array
    mid = (start + end) // 2
    
    # Aplicar o algoritmo recursivamente às duas metades
    left_min, left_max = max_min_select(arr, start, mid)
    right_min, right_max = max_min_select(arr, mid + 1, end)
    
    # Comparar os resultados para obter o mínimo e máximo globais
    overall_min = left_min if left_min < right_min else right_min
    overall_max = left_max if left_max > right_max else right_max
    
    return (overall_min, overall_max)

def max_min_select_wrapper(arr):
    """
    Função auxiliar que adapta a entrada para a função principal.
    Garante compatibilidade com arrays vazios.
    """
    if not arr:
        return (None, None)
    
    return max_min_select(arr, 0, len(arr) - 1)

Explicação Passo a Passo

1. Um único elemento: Quando o intervalo possui apenas um item, ele é automaticamente o menor e o maior (linhas 14-15).

2. Dois elementos: Com apenas dois itens, basta uma única comparação para decidir os extremos (linhas 18-20).

3. Divisão: O vetor é particionado ao meio (linha 26), reduzindo o problema a subproblemas menores.

4. Conquista: Cada parte é resolvida recursivamente (linhas 29-30), retornando seus respectivos mínimos e máximos.

5. Combinação: As respostas parciais são comparadas (linhas 33-34) para obter os resultados finais com apenas duas comparações adicionais.

Como Rodar o Projeto

Requisitos

• Python 3.6 ou versão mais recente

Passos para Execução

1. Baixe ou clone este repositório, garantindo que o arquivo main.py esteja presente.

2. No terminal, execute o seguinte comando:

   python main.py

Demonstração de Uso

# Exemplo de execução
arr = [3, 7, 1, 9, 5, 2, 8, 4, 6]
min_val, max_val = max_min_select(arr, 0, len(arr) - 1)
print(f"Menor valor: {min_val}")
print(f"Maior valor: {max_val}")

Análise Técnica

Complexidade por Contagem de Comparações

Este algoritmo segue a abordagem de dividir o problema em duas partes iguais:

1. Divisão: A lista é repartida em duas metades de tamanho n/2.
2. Combinação: Os resultados intermediários são comparados com apenas 2 comparações.

A recorrência para o número de comparações é:

T(n) = 2T(n/2) + 2

Para os casos iniciais:

• T(1) = 0 (sem comparações)
• T(2) = 1 (uma única comparação)

Desenvolvendo a fórmula:

T(n) = 2T(n/2) + 2
     = 2[2T(n/4) + 2] + 2 = 4T(n/4) + 4 + 2
     = 8T(n/8) + 8 + 4 + 2
     = ...

Ao realizar k divisões, com n/2^k = 1 (ou seja, k = log₂n):

T(n) = n * T(1) + 2(n - 1) = 2n - 2

Portanto, o algoritmo executa no tempo linear, com um total de 2n - 2 comparações.

Complexidade via Teorema Mestre

A equação da recorrência é:

T(n) = 2T(n/2) + O(1)

Identificando os parâmetros:

• a = 2 (quantidade de subproblemas)
• b = 2 (fator de divisão)
• f(n) = O(1) (trabalho feito fora das chamadas recursivas)

Cálculo:

• log₂(2) = 1
• f(n) ∈ O(n^0), e como 0 < 1, aplicamos o Caso 1 do Teorema Mestre

Resultado:

T(n) = Θ(n)

Logo, a complexidade assintótica do algoritmo MaxMin Select é Θ(n), validando a análise feita anteriormente com base na contagem de operações.