Prova NCE-UFRJ - 2005 - BNDES - Profissional Básico - Análise de Sistemas - Desenvolvimento

Questão 1891

• Banca: NCE-UFRJ
• Órgão: BNDES
• Ano: 2005
• Provas: NCE-UFRJ - 2005 - BNDES - Profissional Básico - Análise de Sistemas - Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

Considere uma árvore binária de busca com n elementos e altura mínima. O tempo de acesso a qualquer elemento desta árvore é da ordem de:

• A. O(n)
• B. O(n²)
• C. O(log₂ n)
• D. O(log₁₀ n)
• E. O(nⁿ)

Gabarito: C

Comentários

• Está questão deveria ser anulada, pois todas as alternativas estão corretas.
  A notação O significa o seguinte:
  Dadas duas funções positivas quaisquer, f e g
  f(n) = O(g(n)) se e somente se
  Existe um número real K e um número real n0 tal que f(n) <= K . g(n) para todo n > n0.
  Em palavras: para n suficientemente grande a função g multiplicada por uma constante sempre será um limite superior de f.
  Como já foi explicado acima, o tempo de acesso no caso do exercício é da ordem O(log n).
  O problema é que a função:
  1: f(n) = n é um limite superior de g(n) = log n, pois para n grande n > log n, logo log n = O(n) e a letra A é correta.
  2: f(n) = n2 é um limite superior de g(n) = log n, pois para n grande n2 > log n, logo log n = O(n2) e a letra B é correta.
  3: log n = O(log2 n) e a letra C é correta.
  4: log10 n = log2n/log210 (propriedade de logaritmos) como 1/log210 é uma constante log10 n = K log2n, log10n = O(log2n) logo a letra D é correta. Isso é importante para perceber que não importa a base do logaritmo nas notações Omega, Theta e O.
  5: f(n) = nn é um limite superior de g(n) = log n, pois para n grande nn > log n, logo log n = O(nn) e a letra E é correta.

• A questão deveria ser anulada porque não define o que é altura mínima. Caso a árvore fosse uma AVL ou Vermelho e Preto a resposta estaria correta. No entanto, poderia ser por exemplo esta árvore [1] -> [2] -> [3] -> [4] -> [5] - > [6] e assim por diante. Neste caso o tempo seria O(n).

• c-

  In a binary search tree, the left child of a node has a lesser value than the parent whereas the right child has a greater value than the parent. If there are n nodes in a binary search tree, the maximum height is n-1 and minimum height is ceil(log2n).

  https://www.geeksforgeeks.org/relationship-number-nodes-height-binary-tree/