Questão FC266063
Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona
Algoritmos e Lógica de Programação
IDECAN · 2019
Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona se o vetor estiver ordenado. Assinale a alternativa que indique a ordem de complexidade do pior caso da Busca Binária em um vetor de n números ordenados.
- O(n)
- O(n log n)
- O(log n)
- O(1)
- O(n^2)
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A Busca Binária usa o princípio da divisão e conquista: a cada comparação ela elimina metade do espaço de busca porque o vetor está ordenado.
Se o vetor tem \(n\) elementos, após \(k\) comparações restam no máximo \(n/2^k\) posições possíveis para o elemento buscado. Para reduzir esse número a 1 ou menos, precisamos de
\( \displaystyle \frac{n}{2^k} \le 1 \Rightarrow k \ge \log_2 n.\)
Assim, no pior caso o número de comparações cresce proporcionalmente a \(\log n\). Por isso o tempo assintótico é O(log n) (a base do log é irrelevante para notação assintótica).
Essa eficiência depende de o vetor estar ordenado; constantes e termos menores são desprezados na notação assintótica.
Conteúdo do catálogo FC Concursos · Atualizado em