O que é mais eficiente: uma busca seqüencial ou uma busca binária? Explique.
Passo 1
O enunciado pergunta qual é mais eficiente entre busca sequencial e busca binária. O conteúdo envolve algoritmos de busca em vetores e análise de complexidade de tempo. Para resolver, precisamos entender como cada algoritmo percorre o vetor, quais pré-condições são exigidas (como ordenação) e comparar suas ordens de crescimento usando a notação assintótica.
Passo 2
Na busca sequencial, o algoritmo percorre os elementos um a um, comparando cada valor com o alvo até encontrá-lo ou até terminar o vetor. Não há pré-condição de ordenação, mas no pior caso examinamos todos os
elementos. Assim, o tempo de execução no pior caso cresce linearmente com o tamanho do vetor:
Passo 3
Na busca binária, o vetor deve estar previamente ordenado. O algoritmo compara o valor do meio do intervalo atual com o alvo e elimina metade dos elementos a cada iteração. Logo, o número máximo de comparações é da ordem de
, e o tempo de execução no pior caso é
Isso pressupõe acesso aleatório aos elementos em tempo constante.
Passo 4
Comparando as ordens de crescimento, temos
Portanto, a busca binária é assintoticamente mais eficiente em tempo quando o vetor está ordenado e permite acesso aleatório. A busca sequencial só é vantajosa se o vetor não estiver ordenado e não compensar o custo de uma ordenação, ou em vetores muito pequenos.
Resposta
A busca binária é mais eficiente em termos de tempo assintótico
contra
, desde que o vetor esteja ordenado e haja acesso aleatório aos elementos.