Please enable JavaScript.

Coggle requires JavaScript to display documents.

M1 (Tabelas de Espalhamento, Recursividade, Decrease-and-Conquer, Arvores…

- - - - -
        
        Se a tabela está muito cheia a busca sequencial pode levar a um número muito
        
        grande de comparações.
        
        S No pior caso (N elementos ocupados), deve-se percorrer os N elementos antes
        
        de encontrar o elemento ou concluir que ele não está na tabela.
        
        S A grande desvantagem da Lista Linear é o aparecimento de agrupamentos.
        
        S Uma forma de permitir um espalhamento maior é fazer com que o
        
        deslocamento em vez de 1 seja dado por uma segunda função de hash.
        
        S Essa segunda função de hash tem que ser escolhida com cuidado, não deve
        
        gerar um valor nulo (loop infinito).
        
        S Deve ser tal que a soma do índice atual com o deslocamento (módulo N) dê
        
        sempre um número diferente até que os N números sejam verificados.
        
        S Para isso N e o valor desta função devem ser primos entre si.
        
        Soluções
        
        -
        
        (C1+2C2) %N, depois (C1+3C2) %N, etc.
        
        S Para calcular o terceiro índice (se também houver colisões) usa-se
        
        S Para calcular o segundo índice ( se existir colisões) usa-se (C1+C2) %N;
        
        S Para calcular o primeiro índice usa-se C1;
        
        S h2(x) = ( x % N-1 )+1 = C2 → usada quando há colisões
        
        S h1(x)=( x % N ) = C1
        
        usar quando há colisões.
        
        Existem duas funções de Hash: Uma para usar normalmente e outra para
  - - - a tabela hash pode
      - tabela;
      - não há nenhuma lista e nenhum elemento armazenado fora da
      - Diferença do encadeamento:
      - não encontrá-lo.
      - posições na tabela até encontrarmos o elemento desejado... ou
      - Ao procurar por um elemento, examinamos sistematicamente as
      - dinâmico ou null.
      - Ou seja, cada entrada da tabela contém um elemento do conjunto
      - armazenados na própria tabela hash.
      - No endereçamento aberto, todos os elementos estão
    - - http://www.each.usp.br/digiampietri/ACH2002/notasdeaula/16-hash3.pdf
- - - - Input -> Um número não negativo inteiro
        Output: the value of n!
        if n = 0 return 1
        else
        return F(n - 1 ) * n
    - - M(n) = M(n − 1) + 1 + M(n − 1) for n > 1.
        = 2^n − 1.
        
        Representação
      - https://www.youtube.com/watch?v=2OxEjrzWq6g