Existe alguma alternativa à busca linear para busca em listas não ordenadas?
2
respostas
respostas
Existe alguma alternativa para busca em listas não ordenadas?
Olá Rafael,
A resposta curta é que não existe uma alternativa eficiente.
Se temos uma lista que não temos interesse em ordernar, precisamos obrigatoriamente passar por todos os elementos da lista pra nos certificar de que encontraremos o que estamos procurando. Isso é porque os elementos não tem nenhuma relação de ordenação conhecida para nos ajudar a buscar. O que leva a um tempo de busca linear O(n).
Por isso preferimos usar listas ordenadas. Pois podemos pesquisar de forma mais inteligente, usando a ordem das posições dos elementos. Dessa forma, podemos fazer a busca em O(log n), que é bem mais rápido.
Olá Rafael,
Esta dúvida ficou mais clara?
Bons estudos!