No contexto de estruturas de dados, considere uma lista encadeada L, não ordenada, contendo N elementos. A complexidade do algoritmo de inserção nessa lista é:
- A)log N;
Errada, porque log N não é a complexidade típica de inserção em lista encadeada não ordenada.
- B)N;
Errada, pois N indica percurso linear, algo desnecessário para inserir em lista não ordenada.
- C)N log N;
Errada, já que N log N é complexo de algoritmos bem diferentes, não de uma inserção simples nessa estrutura.
- D)N2;
Errada, porque N2 é custo muito acima do necessário e não corresponde à operação de inserção na lista.
- E)1.
Certa, porque a inserção pode ser feita em tempo constante, sem varrer os N elementos da lista.
Gabarito: E
Em uma lista encadeada não ordenada, inserir um novo elemento costuma ser bem tranquilo: você cria o nó e o encaixa no início da lista, ou em outra posição já conhecida, sem precisar procurar lugar certo por causa de ordenação. Como não há exigência de manter a lista ordenada, não existe varredura obrigatória pelos N elementos antes da inserção. Por isso, a operação de inserção tem complexidade constante, isto é, O(1). Em termos práticos, o trabalho é sempre o mesmo, independentemente do tamanho da lista: alterar alguns ponteiros e pronto. É aquele tipo de operação que não cresce com N, o que é ótimo para quem gosta de eficiência sem drama. A pegadinha aqui é confundir inserção em lista encadeada com inserção em estrutura ordenada. Se a lista fosse ordenada, você poderia precisar percorrer a estrutura para achar a posição correta, o que levaria a custo linear. Mas, sendo não ordenada, essa busca não existe. Então o gabarito é E, porque a inserção em lista encadeada não ordenada é feita em tempo constante, O(1).