Question

Sobre listas sequenciais e listas encadeadas, é correto afirmar que: Para a busca binária funcionar com desempenho em tempo O(log n), precisamos da propriedade de que cada elemento possa ser acessado em tempo constante dado o índice. Nesse caso, é requerida uma lista linear sequencial, não sendo interessante usar lista encadeada. Em um vetor alocado dinamicamente, podemos aumentar ou diminuir o número de elementos. Nesse caso, é mais fácil alocar vetores com "new" do que estaticamente. Quando temos uma lista encadeada, o acesso a cada elemento, dado o índice, ocorre em tempo constante. Um vetor alocado estaticamente pode ser chamado de lista linear sequencial, pois a ordem lógica é igual à ordem física. O mesmo não ocorre com vetores alocados dinamicamente, pois estes podem ter seus elementos em lugares diversos na memória. Em uma lista encadeada, a ordem lógica dos elementos não corresponde ao posicionamento destes em memória. Por conta disso, é possível fazer acesso a qualquer elemento da lista em tempo constante.

Answer 1

Resposta:

Para a busca binária funcionar com desempenho em tempo O(log n), precisamos da propriedade de que cada elemento possa ser acessado em tempo constante dado o índice. Nesse caso, é requerida uma lista linear sequencial, não sendo interessante usar lista encadeada.

Explicação: