PESQUISA_ORDENACAO_E_TECNICAS_DE_ARMAZENAMENTO_UNIDADE_1

Prévia do material em texto

CENTRO UNIVERSITÁRIO DAS FACULDADES 
METROPOLITANAS UNIDAS – FMU 
 
 
 
 
ENGENHARIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
 
 
 
GABRIEL MOURA DOS SANTOS 
 
 
 
 
RELATÓRIO: DISSERTAÇÃO ARGUMENTATIVA 
 
 
 
 
 
 
 
 
 
São Paulo 
2024 
 
 
ATIVIDADE 1 
 
Ao longo da Unidade foram abordados: a problemática do crescimento do volume de 
dados; conceitos e técnicas sobre algoritmos de busca, ordenação e 
armazenamento; bem como análise de complexidade. Os referidos algoritmos são 
recursos importantes que possibilitam melhor aproveitamento da grande quantidade 
de informação armazenada nos repositórios de dados. Estes assuntos 
proporcionaram a você uma ampla visão sobre o tema, sua aplicabilidade e 
importância no cenário tecnológico atual. (MANZANO, J. A. N. G.; LOURENÇO, A. 
E.; MATOS, E. Algoritmos - Técnicas de Programação. 2. ed. São Paulo: Érica, 
2015.) 
Com base no material que você estudou, escreva sobre algoritmos de busca 
sequencial e binária, dando exemplos e buscando apresentar as diferenças. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Resposta 
Algoritmos de busca são fundamentais no processamento de dados, especialmente 
quando lidamos com grandes volumes de informações. Dois algoritmos comuns são 
a busca sequencial e a busca binária. Vamos discutir cada um deles, destacando 
suas características e diferenças. 
1. Busca Sequencial: 
• Na busca sequencial, os elementos são examinados um por um, do início ao 
fim da lista, até que o elemento desejado seja encontrado ou até que toda a 
lista seja percorrida. 
• É uma abordagem simples e direta, adequada para listas não ordenadas ou 
quando não há informações adicionais sobre a distribuição dos elementos na 
lista. 
• No entanto, seu desempenho é proporcional ao tamanho da lista. Em média, 
a busca pode exigir examinar metade dos elementos da lista para encontrar o 
item desejado. 
Exemplo de busca sequencial em Python: 
def busca_sequencial(lista, elemento): 
 for i in range(len(lista)): 
 if lista[i] == elemento: 
 return i # Retorna o índice se o elemento for encontrado 
 return -1 # Retorna -1 se o elemento não estiver na lista 
 
 
 
 
 
2. Busca Binária 
• Na busca binária, a lista deve estar ordenada previamente. O algoritmo 
compara o elemento desejado com o elemento no meio da lista. Se forem iguais, 
a busca termina. Caso contrário, o algoritmo decide se o elemento está na 
metade inferior ou superior da lista e descarta a metade onde o elemento não 
pode estar. 
• A busca binária é muito mais eficiente do que a busca sequencial para listas 
grandes, pois reduz pela metade o número de elementos que precisam ser 
examinados a cada iteração. 
Exemplo de busca binária em Python: 
def busca_binaria(lista, elemento): 
 inicio = 0 
 fim = len(lista) - 1 
 while inicio <= fim: 
 meio = (inicio + fim) // 2 
 if lista[meio] == elemento: 
 return meio # Retorna o índice se o elemento for 
encontrado 
 elif lista[meio] < elemento: 
 inicio = meio + 1 
 else: 
 fim = meio - 1 
 return -1 # Retorna -1 se o elemento não estiver na lista 
 
 
3. Diferenças 
• A busca sequencial não requer que a lista esteja ordenada, enquanto a busca 
binária exige que a lista esteja ordenada. 
• A busca sequencial é mais simples de implementar, mas pode ser menos 
eficiente em grandes conjuntos de dados. Já a busca binária é mais complexa, 
mas é muito mais eficiente, especialmente em listas grandes. 
• A complexidade de tempo da busca sequencial é O(n), onde n é o tamanho 
da lista. Enquanto a complexidade de tempo da busca binária é O(log n), o que 
significa que seu desempenho melhora exponencialmente com o aumento do 
tamanho da lista. 
Em resumo, a escolha entre a busca sequencial e a busca binária depende das 
características dos dados e dos requisitos de desempenho do sistema.