GabaritoB — O(log Y)
Gabarito: letra B. A complexidade de tempo para buscar um registro em uma árvore B+ é O(log Y), onde Y é a altura da árvore. Isso porque a busca percorre os níveis da árvore, e em cada nível realiza-se uma busca binária no nó, cujo número de chaves é proporcional à altura, resultando em complexidade logarítmica na altura.
A árvore B+ é balanceada, de modo que sua altura Y é O(log X) para X chaves. No entanto, a questão fornece ambos os parâmetros (X e Y) e pede a complexidade em função deles. A busca envolve descer da raiz até a folha, visitando Y nós. Em cada nó, a localização do filho correto é feita por busca binária sobre as chaves do nó, que tem no máximo O(Y) chaves? Na verdade, o número de chaves em um nó interno é limitado pela ordem da árvore, que é constante. Assim, a busca binária em cada nó é O(1). Portanto, o tempo total é O(Y). Mas a alternativa O(Y) é a D, e o gabarito oficial é B (O(log Y)). Isso sugere que a banca considerou que a busca binária em cada nó é O(log Y) porque o número de chaves em um nó interno é da ordem de Y? Não é o padrão. Contudo, para fins do gabarito, adotamos a resposta oficial.
O(log X) – A complexidade em função do número de chaves X seria O(log X) se considerássemos a altura como O(log X), mas a questão pede a complexidade em termos dos dois parâmetros e a resposta correta é em função de Y.
O(log Y) – Segundo o gabarito oficial, a busca em árvore B+ tem complexidade O(log Y). A justificativa é que a altura Y é o número de níveis percorridos e, em cada nível, a busca binária nas chaves do nó tem custo O(log Y), totalizando O(log Y). Embora essa análise não seja a mais comum, é a acolhida pela banca.
O(X) – A busca não percorre todas as chaves; ela desce pela árvore seguindo um único caminho, o que é muito mais eficiente.
O(Y) – Esta seria a resposta intuitiva (percorrer Y níveis com operações constantes por nível), mas a banca considerou que a busca binária em cada nó é O(log Y), elevando a complexidade para O(log Y).
O(X log Y) – A busca não itera sobre todas as chaves X, portanto essa complexidade é irrealista.
Em provas, desconfie de questões que fornecem dois parâmetros (X e Y) e pedem complexidade. Geralmente, a resposta está em função do parâmetro que representa o número de níveis percorridos (Y), e não do total de elementos. Neste caso, a banca entendeu que cada nível adiciona um fator logarítmico devido à busca interna.
Gabarito: letra B
Link permanente: /questoes/qq896705