Flashcard FC268571
De acordo com o assunto TI Desenvolvimento de Sistemas: Algoritmos e Lógica de Programação, responda: Em uma coleção ordenada, compare a complexidade no pior caso entre a busca que
Algoritmos e Lógica de Programação
IDECAN · 2022
Em uma coleção ordenada, compare a complexidade no pior caso entre a busca que examina elementos sequencialmente e a busca que elimina metade do espaço de busca a cada comparação.
Mostrar resposta e comentário
Resposta
De forma objetiva.Busca sequencial: \(O(n)\).
Busca que elimina metade: \(O(\log n)\).
Explicação:
A busca sequencial pode precisar verificar todos os \(n\) elementos no pior caso, daí \(O(n)\).
A busca que elimina metade usa a ordenação para reduzir o espaço pela metade a cada comparação, levando a \(O(\log n)\) no pior caso; exige acesso eficiente ao elemento do meio.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/266060
Conteúdo do catálogo FC Concursos · Atualizado em