Divisão e Conquista

Divisão e Conquista

1. 1- Divisão

   • Responsável por dividir o problema e resolver recursivamente.

2. 2- Conquista

   • Responsável por conquistar os subproblemas.

3. 3- Combinação

   • Responsável por combinar ás soluções dos subproblemas, na solução do problema original.

4. Mergesort

   • Algoritmo de ordenação por comparação utilizando o método dividir para conquistar. O mesmo divide os problemas em subproblemas e os resolve através da recursividade. Utiliza a ordenação por intercalação.

5. Subarranjo Máximo

   • É um problema computacional que pede para que seja encontrado a uma subsequência de números cujo valor seja máximo. De forma que ele vai buscar uma forma de sempre pegar o maior valor. 

6. Recursividade

   • São algoritmos que chamam a si mesmos para resolver um problema.

7. Relação de Recorrência

   • São equações de igualdade ou desigualdade que define uma função em termos de seu valor para entradas menores.
   • Substituição
     • É responsável por arriscar um palpite para um limite e usar indução matemática para provar o palpite.
   • Árvore
     • Faz a conversão da recorrência em uma árvore que retrata os custos de diversos níveis de recursão. Ou seja cada nó da árvore representa o curto de um único subproblema.
   • Mestre
     • Aplica limite ás recorrências.

Images and files in the map