Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(1.4) Estruturas de dados fundamentais (35 -37)
Conjuntos (sets)
Coleção não ordenada (até vazia) de elementos distintos
Forma de definir
Listando os elementos
Especificando uma propriedade
Operações
Checar se um item pertence ao conjunto
Achar a união de dois conjuntos
Achar a intersecção de dois conjuntos
Formas de implementar
Conjuntos que são subconjuntos de um conjunto Universal (U)
Vetor de bits
Implementação rápida
Usa grande quantidade de armazenamento
Usar a estrutura de lista para indicar os elementos do conjunto
Conjuntos finitos
Mais usada
Conjunto não pode conter elementos idênticos
multiset ou bag
Conjuntos são os mesmos independente da ordem
Manter lista ordenada na aplicação
Dicionários
Implementa operações para os conjuntos e multisets
Procurar por um item
Adicionar um novo item
Deletar um item
Busca em um ambiente dinâmico
Formas de implementar
Uso não sofisticado de Arrays
Formas sofisticadas: Hashing e busca em árvores balanceadas
Problema da união de conjuntos
Tipo de dados abstrato (ADT)
Relação entre dados e operações
Conjunto de objetos abstratos com uma coleção de operações
Programação orientada ao objeto
Classes
Space and Time Trade-Offs (Cap. 7) (253–254, 269–274)
Input enhancement
Preprocessar o problema da entrada
Guardar as informações adicionais para acelerar a resolução do problema
Prestructuring
Espaço extra para facilitar acesso mais rápido ou mais flexível para os dados
Processamento feito antes do problema em questão
Estruturamento
Ex: Hashing
Programação dinâmica
Guardar soluções
Tempo e espaço não precisam competir um com o outro
Compressão de dados
(7.3) Hashing
Forma eficiente de implementar dicionários
Uso mais comum é o de registros
Uma chave que diferencia as entidades
Distribuir chaves entre uma array unidimensional
Tabela hash
Função hash
Atribui um valor entre 0 e m-1
Endereço hash
Requisitos
Tabela hash não tão grande comparada com o número de chaves
Distribuição das chaves feita de forma uniforme pela função hash
Função hash precisa ser fácil de computar
Colisão
Duas (ou mais) chaves na mesma célula
Mecanismo de solução para colisões
Tipos
Open Hashing (Separate Chaining)
Chaves guardadas em listas ligadas em células de uma tabela hash
Load factor
α = n/m
n chaves e m células
Eficiência depende do tamanho da lista ligada
E da qualidade da função hash
Load Factor próximo de 1 é o ideal
Busca é realizada de forma parecida a criação
Lista ligada é percorrida em busca da chave inserida
Deletar e inserir são parecidas com a busca
Se o Load Factor é 1
A eficiência das operações é Θ(1)
Closed Hashing (Open Addressing)
Chaves guardadas na tabela hash sem o uso de listas ligadas
Soluções para colisão
Linear probing
Checa a célula após a que a colisão ocorre
Cluster
Sequência contígua de células ocupadas
Reduz a eficiência
Solução
Double hashing
2 more items...
Operações
Busca e inserção
Se a célula não estiver vazia, compara K com a próxima célula
Deletar
Lazy deletion
Marcar os lugares previamente ocupados
Comparação com árvores balanceadas de busca
Eficiência temporal assintótica
Hashing
Caso médio: Θ (1)
Pior caso: Θ (n)
Árvores balanceadas de busca
Caso médio ou pior: Θ (log n)
Preservação na ordenação
Diferente das árvores balanceadas de busca
Hashing não assume a existência de ordem entre as chaves
Hashing menos adequado para aplicações que precisam da ordem
Extendible hashing
Guardar Dicionários grandes em discos
Bucket