Questão 2743177

• Banca: FGV
• Órgão: MPE-AL
• Ano: 2018
• Provas: FGV - 2018 - MPE-AL - Analista do Ministério Público - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A complexidade do algoritmo de busca binária, sobre uma lista indexada ordenada pela chave de busca, é

• A. (N)
  
• B. (log₂ N)
  
• C. (2 log₂ N)
  
• D. (N log₂ N)
  
• E. (N²)
  

Gabarito: B

Comentários

• Gabarito B

  Custo para inserção e remoção de um item
  ▸ A inserção ocorre sempre em uma folha
  ▸ Deve-se percorrer portanto a altura h da árvore
  ▸ Como a árvore pode estar degenerada, no pior caso, a inserção é O(n)
  ▸ No melhor caso O(log n)
  ▸ Remoção
  ▸ Primeiro localiza-se o elemento a ser retirado O(h)
  ▸ Caso recaia no caso 3, deve-se procurar também o elemento a
  substituir o nó a ser retirado O(h)
  ▸ No pior caso tem-se O(n) para uma árvore degenerada
  ▸ No melhor caso O(log n)

   

   

  "Retroceder Nunca Render-se Jamais !"
  Força e Fé !
  Fortuna Audaces Sequitur !

• Complexidade da busca binária: O(log N)

  Complexidade da busca sequencial: O(N)

• Força Guerreiro!!!!!!