Please enable JavaScript.

Coggle requires JavaScript to display documents.

M7 (7.3 Hashing, Space and Time Trade-Offs, Capítulo 1) - Coggle Diagram

- - - - Armazenamento de chaves em listas encadeadas.
      - Eficiência depende do comprimento das listas.
    - - Armazenamento direto na tabela, sem listas.
      - Estratégias de resolução de colisões: Linear Probing, Double Hashing.
      - Desafios: clustering e necessidade de rehashing.
  - - - Média de acessos em buscas bem-sucedidas e mal-sucedidas.
      - Comparação com busca sequencial em lista encadeada.
      - Load factor como fator crucial.
    - - Double Hashing como alternativa.
      - Dificuldades na análise matemática.
      - Linear Probing e seus desafios.
  - - - Hashing: (1) no caso médio, (n) no pior caso.
      - Árvores balanceadas: (log n) no caso médio e no pior caso.
    - - Hashing geralmente não assume ou preserva a ordem das chaves.
- - - - Armazenamento em tabelas.
      - Utilizado historicamente antes dos computadores eletrônicos.
      - Pré-cálculo de valores da função.
    - - Utilização de pré-processamento para acelerar a busca.
      - Simplificação sugerida por Horspool.
  - - - Uso de espaço extra para acesso mais rápido e flexível aos dados.
      - Processamento prévio antes da resolução do problema.
    - - Estruturação do acesso aos dados antes da resolução do problema.
      - Uso de espaço adicional para otimização.
  - - - Em alguns casos, algoritmos podem minimizar tanto o tempo de execução quanto o espaço consumido.
      - Exemplo: Uso de estrutura de dados eficiente para representar a entrada de um problema.
    - - Dependência da eficiência em tempo dos algoritmos de busca (DFS e BFS) na representação do grafo (matriz de adjacência vs. lista de adjacência).
      - Caso de grafos esparsos favorece a lista de adjacência.
      - Exemplo: Travessia de grafos.
  - - - Área importante relacionada à troca entre espaço e tempo.
      - Objetivo: Redução de tamanho.
      - Discussão de um algoritmo de compressão no próximo capítulo.
- - - - Definição
        
        Coleção não ordenada de elementos distintos.
      - Representação
        
        Listagem explícita de elementos ou por propriedade (por exemplo, números primos menores que 10).
      - Operações Importantes
        
        União de conjuntos.
        
        Interseção de conjuntos.
        
        Verificação de pertinência.
    - - Bit Vector Representation
        
        Uso de vetor de bits para representar conjuntos.
        
        Rápida implementação de operações, mas pode exigir muito armazenamento.
        
        Conjuntos como subconjuntos de um conjunto universal.
      - Lista de Estrutura
        
        Adequado para conjuntos finitos.
        
        Ênfase na distinção e ordem dos elementos.
        
        Representação de conjuntos usando listas.
    - - Unicidade de Elementos
        
        Conjuntos não podem conter elementos idênticos.
        
        Listas podem ter elementos duplicados.
      - Ordenação de Elementos
        
        Conjuntos são não ordenados.
        
        Listas são ordenadas.
    - - Relação com problemas de pesquisa dinâmica.
      - Compromisso entre eficiência de pesquisa e eficiência de outras operações.
      - Implementa operações de busca, adição e remoção.
      - Diversas implementações possíveis: arrays, hashing, árvores de busca balanceadas.
    - - Operações de união e pesquisa intercaladas.
      - Soluções eficientes discutidas na Seção 9.2.
      - Inicialização com n conjuntos de um elemento.
    - - Definição
        
        Conjunto de objetos abstratos com operações específicas.
      - Exemplos
        
        Fila de prioridade, dicionário.
      - Implementação
        
        Implementação facilitada em linguagens orientadas a objetos como C++ e Java.