Questão 66491

Um professor de programação iniciante para o ensino médio, chamado Felipe, está ensinando o conceito de estruturas de dados e percebe que os alunos têm dificuldade em entender a diferença prática entre usar uma lista (array) e um dicionário (hash map / tabela de dispersão) para armazenar e recuperar informações. Para eles, ambas as estruturas parecem apenas 'lugares para guardar coisas'. Com o objetivo de criar uma demonstração clara dos trade-offs de desempenho, Felipe elabora uma atividade prática em Python. Ele se baseia em um princípio fundamental da ciência da computação: "A eficiência de um algoritmo depende criticamente da estrutura de dados subjacente. Para a tarefa de buscar um elemento, uma lista não ordenada exige uma busca linear, com complexidade de tempo $O(n)$, pois, no pior caso, é preciso percorrer todos os $n$ elementos. Um dicionário, por outro lado, utiliza uma função de hash para mapear chaves a posições em um array, permitindo o acesso, em média, em tempo constante, $O(1)$, independentemente do tamanho da estrutura." Felipe então cria um grande conjunto de dados com 1 milhão de registros de alunos, onde cada aluno tem um número de matrícula (ID) único e um nome. Ele propõe duas tarefas aos alunos:

Tarefa 1: Armazenar os dados em uma lista de tuplas `[(ID1, Nome1), (ID2, Nome2), ...]` e escrever uma função para encontrar o nome de um aluno dado o seu ID.

Tarefa 2: Armazenar os dados em um dicionário `{ID1: Nome1, ID2: Nome2, ...}` e realizar a mesma busca.

Ele pede que os alunos meçam o tempo de execução da busca por um ID específico em ambas as estruturas.

Qual é o resultado esperado do experimento e a principal conclusão pedagógica que os alunos devem extrair?