Comentários?
Solução [pdf].
Coelho,
Fiquei com dúvida em relação ao segundo exercício.
O motivo dos dois últimos itens (consumo de tempo para construir a tabela tanto para linear probing quanto separete chaining) são: temos n² porque para percorrer as listas ligadas, vamos somando 1 + 2 + ... + n? E n² em linear probing pela fato do tamanho do array?
Obrigado!
Oi Artur,
Legal que você perguntou.
temos n² porque para percorrer as listas ligadas, vamos somando 1 + 2 + ... + n?
É isso mesmo.
A resposta é baseada naquela função de hash que hash metade das chaves em uma lista e a outra metada na outra.
Portanto, teríamos duas lista de tamanho aproximado n/2. Como STs não tem chaves repeticas, antes de inserirmos uma chave precisamos verificar se ela já está presente na ST.
Para isso devemos pecorrer as listas. O tempo para construir cada lista é 1 + 2 + ... + n/2 ∼ n2/4.
Somando para as duas listas tems n2/2 que é quadrático.
E n² em linear probing pela fato do tamanho do array?
Novamente, a resposta é baseada na função de hash definida.
Como você viu no item (a), essa função rapidamente faz com que tenhamos apenas um cluster (pedaço de vetor contiguo totalemente ocupado).
Assim, para inserir um novo elemento, começando da posição inicial que nos da a função de hash, temos que percorrer praticamente todo o cluster antes de inserir o novo item.
Como quando vamos inserir a i-ésima chave o tamanho do cluster é ∼ i temos que o consumo de tempo total tem é ∼ 1 + 2 + ... + n ∼ n2/2 que é quadrático.
Obrigado!