Durante a análise e o desenvolvimento de sistemas no Tribunal de Justiça do Estado de Rondônia (TJRO), é essencial garantir a eficiência das operações de armazenamento e recuperação de dados. Uma das formas de otimizar essas operações é por meio de algoritmos de ordenação e busca. O conhecimento sobre a complexidade de algoritmos e a escolha da estrutura de dados mais adequada para um determinado problema impacta diretamente no desempenho do sistema. Sobre a complexidade dos algoritmos de ordenação, busca e respectivas estruturas de dados, assinale a afirmativa INCORRETA.
- A)O algoritmo QuickSort tem uma complexidade média de O(n log n).
Correta: o QuickSort tem complexidade média de O(n log n), embora possa piorar em certos cenários.
- B)As tabelas hash oferecem uma busca com complexidade O(1) no pior caso.
Errada: tabelas hash costumam ter busca O(1) em média, mas no pior caso podem degradar para O(n) por colisões.
- C)O algoritmo de ordenação Bubble Sort tem complexidade O(n²) no pior caso.
Correta: o Bubble Sort tem complexidade O(n²) no pior caso.
- D)A busca binária exige que o conjunto de dados esteja ordenado previamente.
Correta: a busca binária exige dados previamente ordenados para funcionar corretamente.
- E)As listas encadeadas não permitem busca eficiente, pois exigem percorrimento sequencial.
Correta: listas encadeadas não têm acesso aleatório, então a busca normalmente é sequencial.
Gabarito: B
Quando a questão mistura ordenação, busca e estrutura de dados, o segredo é lembrar que o desempenho depende tanto do algoritmo quanto da organização dos dados. Em prova, a banca costuma cobrar a ideia central da complexidade: algumas técnicas são rápidas na média, outras só funcionam bem se o dado já estiver em uma certa forma, e algumas estruturas favorecem busca, mas cobram um preço em manutenção ou em casos extremos. No caso das ordenações, o QuickSort costuma ter complexidade média de O(n log n), enquanto o Bubble Sort é aquele clássico mais simples, porém bem menos eficiente, com pior caso O(n²). Já a busca binária só faz sentido se o conjunto estiver ordenado, porque ela pula metades do array com base nessa ordenação. Em listas encadeadas, a busca tende a ser sequencial mesmo, pois não há acesso direto por índice. O ponto-chave da questão está nas tabelas hash. Elas são famosas por oferecer busca muito rápida em média, normalmente próxima de O(1), graças ao uso de função hash e acesso direto ao endereço lógico. Mas dizer que isso acontece no pior caso está errado: se houver muitas colisões, a busca pode degradar bastante, chegando a O(n) em cenários ruins. Por isso, o gabarito é a letra B. A afirmação erra justamente ao transformar em garantia de pior caso algo que é, na verdade, uma vantagem média/esperada da estrutura. Em concursos, a banca adora trocar "média" por "pior caso" para testar se você não caiu no encanto da hash.