SóProvas

ID
1891
Banca
NCE-UFRJ
Órgão
BNDES
Ano
2005
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

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:

Alternativas
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/