Flashcard FC377480
Qual a complexidade de tempo, no pior caso, de um algoritmo que reduz pela metade o espaço de busca a cada comparação?
Algoritmos e Lógica de Programação
Instituto Consulplan · 2024
Qual a complexidade de tempo, no pior caso, de um algoritmo que reduz pela metade o espaço de busca a cada comparação?
Mostrar resposta e comentário
Resposta
O(log n).Explicação:
Após \(k\) divisões resta no máximo \(n/2^k\) elementos.
A busca termina quando \(n/2^k \le 1\), isto é \(k \ge \log_2 n\), logo \(k = \lceil \log_2 n\rceil\).
Como cada passo faz trabalho constante, a complexidade no pior caso é O(log n).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/374710
Conteúdo do catálogo FC Concursos · Atualizado em