Questão 226267

• Banca: CESGRANRIO
• Órgão: EPE
• Ano: 2010
• Provas: CESGRANRIO - 2010 - EPE - Analista de Gestão Corporativa - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Um programador decidiu utilizar, em determinado sistema de análise estatística, uma árvore AVL como estrutura de dados. Considerando-se n a quantidade de elementos dessa árvore, o melhor algoritmo de pesquisa, com base em comparações, possui complexidade de tempo, no pior caso, igual a

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

Gabarito: B

Comentários

• 
  A propósito, o simbolo da ferradura (ÔMEGA) refer-se ao melhor caso, o do sandwich (TETA) ao caso médio e o BIG-O , O(n) ao pior caso.
  
  A  árvore AVL é uma árvore binária de busca balanceada.
  
  Árvores binárias de busca não balanceadas podem - no pior caso - crescer apenas para um lado transformando-se em uma lista. Nesse caso o tempo de busca torna-se O(n), onde n é o tamanho da lista.
  
  No caso da arvore AVL, que garante uma árvore com fator de desbalanceamento no máximo 1, isto á  | alturaDaSubarvoreDireita - alturaDaSubarvoreEsquerda | <= 1 , para todos os nós, o pior caso do algoritmo torna-se O( log n), ou seja, o elemento procurado é uma folha da arvore, e a altura de uma arvore de n elementos é log n.
  
  OBS: log n , sendo log na base 2, não na base 10.

• A complexidade no pior caso a árvore AVL é  O( log n)