Please enable JavaScript.

Coggle requires JavaScript to display documents.

M4 (Levitin) - Coggle Diagram

- - - - No caso bottom-up, resolve-se o problema para uma partição menor do conjunto e a partir dessa resolução define-se a solução para um outro conjunto maior no qual está contida, e assim sucessivamente, unindo as soluções de cada conjunto. Em geral, podem ser entendidos como uma "abordagem incremental", que lembra o processo de indução.
      - Possui 3 variações predominantes:
        
        Redução por uma constante
        
        Ex.:a^n = a^(n-1) * a (no caso a constante é 1)
        
        Redução por um fator constante
        
        Ex.: a^n = (a^(n/2))^2 (no caso o fator constante é 1/2)
        
        Redução de tamanho variável
        
        Ex.: mdc(m, n) = mdc(n, m mod n)
      - No caso top-down, descreve-se como um conjunto maior pode ser resolvido a partir do resultado de um subconjunto menor e assim sucessivamente. Em geral, podem ser entendidos como recursões.
  - - - Insertion Sort
        
        Consiste em uma abordagem incremental na qual o algoritmo de ordenação é aplicado incialmente para um pequeno trecho da sequência da entrada e então acrescenta-se um dos elementos restantes da entrada na nova sequência já ordenada. Assim, vão adicionando-se um a um os elementos a uma sequência ordenada que vai aumentando de tamanho
        
        Ou seja, uma vez que a sequência de tamanho k está ordenada, adiciona-se um novo elemento de tal forma que a nova sequência de tamanho k+1 continue ordenada. O processo se repete até completar a sequência com todos os n elementos da entrada
        
        Embora o algoritmo seja recursivo, é mais eficiente a abordagem incremental (bottom-up)
        
        No pior caso, o número de operações básicas (no caso comparação) é (n-1)n/2 [θ(n^2)], tal qual o selection sort
        
        No caso médio, o número de comparações é aproximadamente (n^2)/4, o que é quase duas vezes mais rápido que o selection sort
        
        No melhor caso, o número de comparações é n-1 [θ(n)] o que é muito mais eficiente em comparação ao selection sort
- - - - 1) Um problema é dividido em diversos outros subproblemas do mesmo tipo - e de preferência com tamanhos iguais
        
        A chamada recorrência geral de Dividir e Conquistar, que representa o tempo total de execução, é: T(n) = aT(n/b) + f(n) em que "a" é o número de partições que precisam ser resolvidas, "b" é o número de partições em que o problema é dividido, "n" é o tamanho do problema (no caso, uma potência de b) e "f(n)" é o tempo necessário para dividir o problema em b partições e combinar as soluções.
        
        O denominado Master Theorem simplifica a análise da eficiência dessa recorrência, apresentando que, se f(n) está em θ(n^d), então T(n) pertence a:
        
        θ (n^d) quando a < b^d
        
        θ [ (n^d) log(n) ] quando a = b^d
        
        θ [ n^( log(a)_(b) ) ] quando a > b^d
      - 2) Os subproblemas são resolvidos, geralmente de maneira recursiva
      - 3) Se necessário, as soluções para os subproblemas são combinadas a fim de se obter uma solução para o problema original
  - - - Mergesort
        
        Consiste em 2 etapas
        
        1) Dividir recursivamente uma sequência em duas subsequências de tamanhos iguais (top-down), repetindo o procedimento com cada subsequência até chegar em subsequências mínimas (geralmente unitárias)
        
        2) Em seguida inicia-se a operação de "mesclagem" (merge) na qual as subsequências mínimas são comparadas duas a duas e agrupadas de maneira ordenada em uma mesma sequência maior que sofre recursivamente a mesma operação de merge com outra sequência ordenada formada. Esse procedimento se repete até que se forme uma sequência ordenada com todos os elementos da entrada
        
        A fórmula recursiva do número de comparações para essa aplicação é C(n) = 2C(n/2) + CM(n), em que CM(n) é o número de comparações durante a etapa merge
        
        No pior caso, o número de comparações na etapa merge é n-1
        
        Assim, a recursão do pior caso será:
        C(1) = 0
        C(n) = 2C(n/2) + n - 1
        
        A solução para essa recorrência é:
        C(n) = n log(n)_(2) - n + 1
        O que condiz com a eficiência θ(n log(n)) estabelecida pelo Master Theorem
        
        Esse número de comparações é muito próximo da quantidade mínima teórica de comparações que qualquer algoritmo de ordenação pode alcançar, o que exprime a grande eficiência desse método.
        
        1 more item...
        
        Uma vantagem do mergesort em relação à outros algoritmos potentes, como o quicksort e o heapsort, é a sua estabilidade.
        
        Uma de suas principais desvantagens é a grande quantidade extra de memória necessária para armazenar as múltiplas subsequências que são formadas.
        
        Duas variações comuns do mergesort são:
        
        Implementação bottom-up, na qual inicia-se já com a operação de merge entre pares de elementos da sequência de entrada (o que alivia um pouco o armazenamento de memória necessário)
        
        Dividir recursivamente em mais partes do que 2 apenas, o que é chamado de multiway mergesort
- - - - Bubble Sort
        
        Mais simples, porém em geral menos eficiente que o Selection Sort, se baseia no procedimento de mover um item para a direita enquanto os que estiverem à direita forem menores do que ele.
        
        O número de vezes que a operação básica (no caso, comparação) ocorre é o mesmo para qualquer entrada de mesmo tamanho n: (n-1)n/2 [θ(n^2)]
        
        O número de trocas é [θ(n^2)] tanto no pior caso quanto no caso médio
      - Selection Sort
        
        Intuitivo, pois se aproxima do procedimento humano comumente realizado, no qual vão sendo identificados e posicionados, um a um, em ordem crescente, os elementos da lista.
        
        O número de vezes que a operação básica (no caso, comparação) ocorre é o mesmo para qualquer entrada de mesmo tamanho n: (n-1)n/2 [θ(n^2)]
        
        Vantagem do insertion sort
        
        O número de trocas é n-1 [θ(n)] no pior caso
        
        Vantagem do Selection Sort