Busca por interpolação 💻

Requisitos do Projeto• Tecnologias • Sobre o Algoritmo • Complexidade • Config. de Teste • Colaboradores •

Requisitos do Projeto

✅A cada execução do programa, ele deve carregar os dados(armazenados em um arquivo texto).
✅O programa deve perguntar ao usuario qual cliente ele deseja buscar por nome ou codigo com o algoritmo Busca por interpolação.
✅Compute o tempo de execução do processo de busca.
✅Informe a complexidade do algoritmo Busca por Interpolação.

Tecnologia Utilizada

Sobre o Algoritmo

O algoritmo de busca por interpolação é uma técnica de busca em estruturas de dados ordenadas que usa uma fórmula de interpolação para estimar a posição do elemento desejado de forma mais precisa do que a busca binária tradicional.

Como Funciona

O algoritmo de busca por interpolação estima a posição do elemento desejado usando uma fórmula e ajusta essa estimativa com base nos valores dos elementos até encontrar o elemento desejado ou determinar sua ausência.

Implementação

  def busca_interpolacao(lista, chave):
      inicio = 0
      tentativas = 1
      fim = len(lista) - 1

      while inicio <= fim and ord(lista[inicio][0]) <= ord(chave[0]) <= ord(lista[fim][0]):
          # calcula a posição utilizando uma média ponderada das posições.
          posicao = inicio + int(((ord(chave[0]) - ord(lista[inicio][0]))/(ord(lista_nomes[fim][0]) - ord(lista[inicio][0]))) * (fim - inicio))
          if lista[posicao] == chave:
              return posicao # chave encontrada
          elif lista[posicao] < chave:
              inicio = posicao - 1
          else:
              fim = posicao - 1

      return -1 # chave não encontrada

Como rodar na minha maquina?

Clone o repositorio na sua maquina:

git clone https://github.com/classroom-ufersa/buscaPorInterpolacaoClientes.git

Para executar você precisa navegar até o diretório onde o arquivo Python está localizado. No terminal use este comando:

python main.py

Complexidade

Pior Caso:

O pior caso ocorre quando a estimativa da posição do elemento não é precisa e o algoritmo se comporta de forma semelhante à busca linear, visitando cada elemento do array. Portanto, a complexidade para o pior caso é O(n).

c1 * 1 + c2 * 1 + c3 * n + c4 * n + c5 * n + c6 * n + c7 * n + c8 * n + c9 * 1 = O(n)

Caso Médio:

No caso médio, a complexidade depende da distribuição dos dados. Se assumirmos que os dados estão uniformemente distribuídos, a complexidade média é aproximadamente O(log(log n)) ou melhor. No entanto, calcular a complexidade exata do caso médio requer uma análise probabilística detalhada da distribuição dos dados.

Melhor Caso:

O melhor caso ocorre quando a interpolação consegue estimar a posição do elemento corretamente desde o início, resultando em uma única iteração. Portanto, a complexidade para o melhor caso é O(1).

c1 * 1 + c2 * 1 + c3 * 1 + c4 * 1 + c5 * 1 + c6 * 1 + c7 * 1 + c8 * 1 + c9 * 1 = O(1)

Configuração usada nos testes

CPU: AMD Ryzen 5 5500U
Frequência: 2.1GHz até 4GHz
Clock base: 100MHz
RAM: 10gb DDR4

Colaboradores

Um agradecimento especial a todas as pessoas que contribuíram para este projeto.

João Gustavo

Antonio Vinícius

Marcelo Augusto

Eduardo Abrantes