Questão 5330437

• Banca: Exército
• Órgão: EsFCEx
• Ano: 2020
• Provas: Exército - 2020 - EsFCEx - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A operação de busca em uma árvore B, no pior caso, tem complexidade de tempo equivalente a:

• A. O(n!)
• B. O(log n)
• C. O(n log n)
• D. O(1)
• E. O(n²)

Gabarito: B

Comentários

• - Uma árvore balanceada, após inclusões, alterações e exclusões, deve manter o custo dessas operações em O(log n).

  - Cada subárvore que contém m nós deve possuir altura igual a O(log n).

  - Árvores balanceadas: árvores AVL, árvore Graduada, árvores B e arvore rubro-negra.

  Alternativa: B

• Complexidade Logarítmica​

  • São os algoritmos de complexidade O(logN).​
  • Ocorre tipicamente em algoritmos que dividem o problema em problemas menores.​
  • Ex.: O algoritmo de Busca Binária

  Resposta: B

• Complementando a resposta dos colegas: Alocação Binaria - 0(log N) / Alocação Sequencial (Vetores/Matrizes) = 0(n)