Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 4 - Coggle Diagram

- - - - As principais variações dessa técnica são:
        
        Diminuir por um fator constante.
        
        Reduzir a instância de um problema pelo mesmo fator constante (geralmente esse fator constante é 2) em cada iteração do algoritmo.
        
        Usando o mesmo exemplo de computar \(a^n\):
        
        Se \(n\) for ímpar, para termos um expoente inteiro deve ser feito o mesmo raciocínio porém partindo de \(n-1\), isso faz ter que multiplicar por \(a\) no final.
        
        Resultando em: \(a^n=(a^{\frac{n-1}{2}})^2\cdot a\).
        
        1 more item...
        
        Se \(n=0\): \(a^n=1\).
        
        Se \(n\) for par, podemos fazer a relação entre uma instância de tamanho \(n\) e outra de tamanho \(\frac{n}{2}\).
        
        Ficamos com: \(a^n=(a^{\frac{n}{2}})^2\).
        
        1 more item...
        
        Diminuição de tamanho variável.
        
        O padrão de redução da instância é variável, mudando em cada iteração.
        
        Diminuir por uma constante.
        
        O tamanho de uma instância é diminuído por uma mesma constante (geralmente essa constante é 1) em cada iteração do algoritmo.
        
        Para computar, por exemplo, \(a^n\), com \(a\) diferente de zero e \(n\) um inteiro não negativo:
        
        top down: a relação entre uma instância de tamanho \(n\) e outra de tamanho \(n-1\) resultaria na definição recursiva de exponenciação: \(a^n=a^{n-1}\cdot a\).
        
        bottom up: multiplicar \(1\) por \(a \ n\) vezes.
        
        É igual ao algoritmo de força bruta, porém é utilizado um pensamento diferente.
  - - - Para isso, se temos um array ordenado de \(n-1\) elementos \(A[0..n-2]\), para inserir o último elemento nele, o \(A[n-1]\), basta procurar no subarray já ordenado, da direita para a esquerda, o primeiro elemento que seja menor ou igual a \(A[n-1]\), e, quando encontrado, inserir \(A[n-1]\) à sua direita.
        
        Esse algoritmo é mais eficientemente implementado por bottom up, iterativamente.
        
        Diferente do algoritmo de ordenação por seleção, aqui os elementos nem sempre estarão em sua posição final antes de terminar a ordenação por completo.
        
        Algoritmo em pseudocódigo de classificação por inserção
        
        while \(j ≥ 0\) and \(A[j ] > v\) do
        
        \(j ← i − 1\)
        
        \(v ← A[i]\)
        
        for \(i ← 1\) to \(n − 1\) do
        
        \(j ← j − 1\)
        
        \(A[j + 1] ← v\)
        
        A operação básica do algoritmo acima é a comparação \(A[j ] > v\) e a quantidade que será feita depende da entrada.
        
        A entrada de pior caso é um array com valores estritamente decrescentes, e o número de comparações para uma entrada assim é:
        
        \(C_{worst}(n)=\frac{(n-1)n}{2}\).
        
        1 more item...
        
        Já a entrada de melhor caso, o caso base só é executado uma vez a cada iteração do laço externo, e acontece quando o array da entrada já está ordenado em ordem não decrescente.
        
        O número de comparações é: \(C_{best}(n)=n-1\).
        
        1 more item...
        
        Na entrada de caso médio, o algoritmo faz em média metade de comparações que em um array decrescente.
        
        \(C_{avg}(n)\approx \frac{n^2}{4}\).
        
        1 more item...
- - - - Selection Sort
        
        De maneira simples, este algoritmo funciona procurando o menor termo de uma lista com \(n\) elementos e colocando-o na primeira posição, trocando de lugar com o que estava nela anteriormente.
        
        Seguindo disso, agora é feita uma busca a partir do segundo elemento, buscando o segundo menor elemento da lista, e, quando este for encontrado, deve ser trocada sua posição com a do segundo elemento.
        
        Fazendo-se isso repetida e sucessivamente, a lista ficará ordenada de maneira não decrescente.
        
        A operação básica do algoritmo é a comparação um a um de cada elemento para saber qual é o menor definitivo para cada troca de posição.
        
        O número de vezes que a operação básica é feita depende do tamanho do array e pode ser encontrada pela fórmula: \( C(n) = \sum_{i=0}^{n-2}(n-1-i)\).
        
        1 more item...
        
        Algoritmo em pseudocógido de ordenação por seleção:
        
        for \(i←0\) to \(n-2\) do
        
        \(min ← i\)
        
        for \(j ← i + 1\) to \(n − 1\) do
        
        if \(A[j ] < A[min]\) \(min ← j\)
        
        swap \(A[i]\) and \(A[min]\)
      - Bubble Sort
        
        Esse algoritmo consiste em comparar elementos adjacentes de uma lista e verificar se eles estão ordenados, e, se não estiverem, eles devem ser ordenados trocando de lugar.
        
        Isso deve ser repetido várias vezes até que todos os elementos estejam ordenados.
        
        O número de comparações feitas para o algoritmo referido acima é o mesmo para qualquer array de mesmo tamanho, e é obtida através da mesma fórmula utilizada para a ordenação por seleção: \( C(n) = \sum_{i=0}^{n-2}(n-1-i)\).
        
        O número de trocas depende da entrada, mas no pior caso ele é o mesmo que o de comparações.
        
        O exemplo de algoritmo acima ainda pode ser muito refinado.
        
        1 more item...
        
        Algoritmo em pseudocódigo de ordenação por bolhas:
        
        for \(i ← 0\) to \(n − 2 do\)
        
        for \(j ← 0\) to \(n − 2 − i\) do
        
        if \(A[j + 1] < A[j ]\) swap \(A[j ]|\) and \(A[j + 1]\)