Flashcard FC268574
Qual a complexidade do pior caso da Busca Binária em um vetor ordenado de n elementos?
Algoritmos e Lógica de Programação
IDECAN · 2019
Qual a complexidade do pior caso da Busca Binária em um vetor ordenado de n elementos?
Mostrar resposta e comentário
Resposta
O(log n)Explicação:
A busca elimina metade do espaço a cada comparação.
Se existem n elementos, após k comparações restam no máximo $$\frac{n}{2^k}$$.
Para reduzir a 1 ou menos: $$\frac{n}{2^k}\le1\Rightarrow k\ge\log_2 n$$.
Portanto, no pior caso são necessárias Θ(log n) comparações, logo a complexidade é O(log n).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/266063
Conteúdo do catálogo FC Concursos · Atualizado em