Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets e Dicionários, Space and time Trade-offs, Vinícius Lima Sá de Melo -…
Sets e Dicionários
Sets basicamente são uma lista de elementos que seguem uma determinada regra e não são ordenados (como um conjunto)
Set Universal é o set que define todos os outros subsets
Um subset pode ser representado de forma binária, Ex: U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, then S = {2, 3, 5, 7}, S = 01101010
Os elementos dos sets são únicos
Um dicionário é um set com operações de busca, deletar um item e adicionar um item
Space and time Trade-offs
O tempo normalmente é inversamente proporcional ao espaço usado
O pré processamento da entrada pode ser importante para a eficiência, e armazenar ele pode aumentar a eficiência temporal mas diminuir a espacial
É verdade mas não necessariamente, tudo depende do problema e do algoritmo utilizado
Hashing
Ex de país, todo mundo tem um CPF único, e esse seria a key, que identifica todos
Hashing se trata de um array unidmensional (hash table) que tem várias keys
Hash adress é o índice da key
Hash function é um função que gera uma key
Tem quer ser fácil de computar
Keys são passíveis de colisão, apontar para o mesmo elemento
No pior caso todas as keys apontarão para a mesma célula
Open Hashing
Keys são armazenadas em linked lists
Ex: Hashing table = {A, FOOL, AND, HIS, MONEY, ARE, SOON, PARTED}
Hashing function: h(A) = 1 mod 13 = 1
Load factor é a relação entre o tamanho da hashing table e qtd de keys, n/m
S ≈ 1 + α/2 and U = α
O ideal é ser próximo de 1, pois muito menor desperdiçaria espaço e muito maior iria ter grandes linked list e tempo maior de procura
Closed Hashing
Não utiliza linked lists
O tamanho tem que ser maior ou igual a quantidade de keys
Quando tem colisão checa a próxima célula livre para indicar a key
A table é tratada como um vetor circular, e caso estejam todas as células ocupadas, abre mais um vaga no início
Quanto mais cheia a tabela fica maior a chance de cluster, em que não tem mais espaços para os elementos da keys
Excluir elementos não é tão simples
Pode se usar a exclusão preguiçosa, em que so se marca os elementos que não vai mais utilizar
Vinícius Lima Sá de Melo - vlsm
