Na resposta o instrutor afirma que o tempo de execução da remoção da lista ligada é linear, pois precisa-se primeiro encontrar o elemento na posição que se deseja remover. Esta operação, de fato, tem tempo linear. Mas, apenas para confirmar: caso a remoção seja do primeiro elemento, então o tempo é constante, correto? Faço essa observação porque a pergunta não deixa claro se a remoção é no meio ou no início. Na resposta, incluí essa ponderação. Obrigado, Artur.
1
resposta
resposta
Dúvida sobre o tempo de remoção na lista ligada
Olá, Artur. Beleza?
A complexidade para realizar operações numa determinada estrutura de dados não é alterada com base no número de elementos no caso concreto.
O conceito de complexidade de tempo leva em consideração o algoritmo usado para operar na estrutura no geral, sem pensar num tamanho específico, pensando de forma abstrata.
Se você executar a remoção de um item que esteja na posição 20 da lista, a tendência é que sempre demore o mesmo tempo para remover itens na posição 20, mas não muda o fato de que, para remover o vigésimo elemento, tivemos de passar pelo 19, 18, 17...
Então, ainda que a lista contenha um elemento só ou removamos o primeiro elemento, a complexidade continua a mesma, pois é definida matematicamente.
Espero ter ajudado. Se tiver dúvidas, é só dizer.