Divisão e conquista
A estrutura de muitos algoritmos eficientes segue
o paradigma
da divisão e conquista.
Esse paradigma (ou estratégia de projeto de algoritmos)
consiste no seguinte:
-
a instância dada do problema
é dividida em duas ou mais instâncias menores,
-
cada instância menor é resolvida
usando o próprio algoritmo que está sendo definido,
-
as soluções das instâncias menores são combinadas
para produzir uma solução da instância original.
Essa estratégia produz um algoritmo eficiente
se o processo de divisão e o processo de combinação
forem suficientemente rápidos
(como acontece, por exemplo,
nos algoritmos
Mergesort
e Quicksort).
Exemplos
Eis alguns algoritmos
que seguem o paradigma da divisão e conquista:
Exercícios
-
Aplique a estratégia da divisão e conquista ao problema de
calcular a soma dos elementos de um vetor A[1..n]
de números inteiros.
Estime o consumo de tempo do algoritmo.
Compare o resultado com o consumo de tempo
do algoritmo trivial de soma.
-
O tamanho das instâncias de um certo problema
é medido por um parâmetro n.
Tenho três algoritmos —
A, B e C —
para o problema:
-
A divide cada instância do problema em cinco subinstâncias
de tamanho ⌊n/2⌋,
resolve as subinstâncias
e então combina as soluções em tempo Ο(n);
-
B divide cada instância do problema em duas subinstâncias
de tamanho n−1,
resolve as subinstâncias
e então combina as soluções em tempo Ο(1);
-
C divide cada instância do problema em nove subinstâncias
de tamanho ⌊n/3⌋,
resolve as subinstâncias
e então combina as soluções em tempo Ο(n²).
Qual o consumo de tempo de cada um dos algoritmos?
Qual dos algoritmo é assintoticamente mais eficiente no pior caso?
