GabaritoB — N;
Gabarito: letra B. No pior caso, a busca por uma chave em uma lista encadeada (mesmo ordenada e circular) exige percorrer todos os N elementos, resultando em complexidade O(N). Não é possível realizar busca binária em listas encadeadas, pois não há acesso aleatório aos elementos.
A questão testa o conhecimento sobre as limitações das estruturas de dados: listas encadeadas, por mais que estejam ordenadas, não permitem acesso direto ao elemento do meio, inviabilizando algoritmos como a busca binária (que teria complexidade O(log N)). Assim, a busca sequencial é a única opção, levando a O(N) no pior caso.
Complexidade constante O(1) só seria possível se a chave estivesse sempre na primeira posição (acesso direto), o que não é garantido no pior caso.
A busca em lista encadeada linear (mesmo circular e ordenada) requer percorrer todos os elementos no pior caso, pois cada nó só tem referência ao próximo. Logo, a complexidade é O(N).
O(log N) é a complexidade da busca binária, que exige acesso aleatório a vetores ordenados. Listas encadeadas não suportam esse tipo de acesso.
O(N log N) é típico de algoritmos de ordenação eficientes (como mergesort), não de busca em lista encadeada.
O(N²) aparece em algoritmos com laços aninhados (ex.: busca em duas listas, ordenação bolha). A busca simples é apenas O(N).
Em listas encadeadas, busca sempre é O(N) no pior caso, independentemente de ordenação ou circularidade. Para busca eficiente em dados ordenados, prefira vetores (com busca binária) ou árvores balanceadas (como AVL).
Gabarito: letra B.
Link permanente: /questoes/fg072431