Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos - Coggle Diagram
Algoritmos
Hashing
Distribuir chaves entre um sistema unidimensional
Hash Function
Gera as chaves
Uma função hash precisa distribuir as chaves entre as células da tabela hash de maneira uniforme.
O tamanho de uma tabela hash não deve ser excessivamente grande em comparação com o número de chaves, mas deve ser suficiente para não comprometer o tempo de implementação.
Uma função hash deve ser fácil de calcular
Open hashing
As chaves são armazenadas em listas vinculadas e anexadas às células de uma tabela hash
Closed hashing
Todas as chaves são armazenadas na própria tabela de hash sem o uso de listas vinculadas
Sets (Conjuntos)
Coleção desordenada de itens distintos (elementos)
Universal set (Conjunto Universal)
Se o conjunto U tiver n elementos, qualquer subconjunto S de U pode ser representado por um vetor de bits de tamanho n, em que o iº elemento é 1 se e somente se o iº elemento de U está incluído no conjunto S, caso contrario o elemento será 0.
Na computação, as operações que precisamos realizar para um set (conjunto) ou multiset
muitas vezes estão entre: procurando por um determinado item, adicionando um novo item e excluindo um item
Estrutura de dados que implementa essas 3 operacoes
Dicionários
Implementação
Eles variam de um uso não sofisticado de arrays (classificados ou não)
a técnicas muito mais sofisticadas, como hash e pesquisa equilibrada em árvores
Podemos usar a estrutura de lista para representar um set
Multisets
Coleção desordenada de itens podendo conter itens iguais
Space and Time Trade-offs
a ideia é pré-processar a entrada do problema, no todo ou em parte, e armazenar as informações adicionais obtidas para acelerar resolver o problema depois.
Input enhancement (Aprimoramento de entrada)
abordagem da pré-estruturação
Usa espaço extra para facilitar o acesso mais rápido e / ou flexível aos dados