Please enable JavaScript.
Coggle requires JavaScript to display documents.
(Compensações de espaço e tempo, Conjuntos e Dicionários) - Coggle Diagram
Compensações de espaço e tempo
input enhancement
as entradas são pré-processadas, salvos os resultados para consultar posteriormente e acelerar a resolução do problema.
prestructuring
usa um espaço extra para facilitar o acesso mais rápido aos dados
dynamic programming
consiste em armazenar as soluções dos subproblemas para resolver o problema
Conjuntos e Dicionários
Conjunto é uma coleção não ordenada
Os valores dentro do conjuntos são chamados de elementos
Podem ser implementados por
Vetor de bits
operações são realizadas de forma rapida
Custo alto de armazenamento
Lista
Um conjuntos não pode ter elementos iguais
este requisito pode ser contornado pelo multiset ou bag
Operações importantes são a união e a interseção
uma estrutura de dados que tem as operações procurar, adicionar e excluir algum elemento do conjunto é chamada de
dicionário
implementação varia geralmente entre
Array
hashing
Maneira muito eficiente de implementar dicionários
Entres os campos, temos a
KEY
Tabela Hash
Vetor que contem as chaves(KEY)
Função Hash
atribui um valor inteiro para cada chave
Esse valor é chamado de
Endereço Hash
A função deve ser fácil de calcular
Deve ter cuidado para evitar
collisions
collisions pode acontecer, principalmente quando a tabela é menor que o numero de chaves
Duas formas de resolução de
collisions
open hashing
as chaves são armazenadas em listas vinculadas as células da tabela
closed hashing
As chaves são armazenadas na tabela Hash
double hashing
usa outra função Hash para determinar um incremento fixo após a colisão
em teste, se apresentou melhor que outras mas quando está perto de ficar cheia, seu desempenho cai
1 more item...
balanced search trees
É um ADT