PAA 03 DivisaoConquista

Projeto e Análise de Algoritmos
Divisão e Conquista

Rodrigo Veras [e-mail] Universidade Federal do Piauí
Centro de Ciências da Natureza
Departamento de Computação

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

1 / 21

Sumário

1

Introdução

2

Recursividade

3

Algoritmo MergeSort

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

2 / 21

Introdução

Sumário

1

Introdução

2

Recursividade

3

Algoritmo MergeSort

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

3 / 21

Introdução

Introdução

Dividir o problema a ser resolvido em problemas menores
(semelhantes);
Resolver os subproblemas recursivamente;
Combinar as soluções;
Geralmente leva a soluções eficientes e elegantes!

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

4 / 21

Introdução

Passo a Passo

Dividir dividir o problema em um determinado número de subproblemas semelhantes;

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

5 / 21

Introdução

Passo a Passo

Dividir dividir o problema em um determinado número de subproblemas semelhantes;
Conquistar conquistar os subproblemas recursivamente até que o tamanho do problema seja pequeno suficiente para uma solução direta;

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

5 / 21

Introdução

Passo a Passo

Dividir dividir o problema em um determinado número de subproblemas semelhantes;
Conquistar conquistar os subproblemas recursivamente até que o tamanho do problema seja pequeno suficiente para uma solução direta;
Combinar combinar as soluções dos subproblemas para formar a solução do problema original.

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

5 / 21

Recursividade

Sumário

1

Introdução

2

Recursividade

3

Algoritmo MergeSort

Rodrigo Veras (UFPI - CCN - DC)

Projeto e Análise de Algoritmos

6 / 21

Recursividade

Conceito

Uma função recursiva é aquela que faz uma chamada a si mesma
(direta ou indireta);