Divisão e conquista
O projeto de muitos algoritmos eficientes
é baseado no método da divisão e conquista.
Esse método (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.
A segunda fase é implementada por uma chamada recursiva.
Essa é a fase da conquista.
O método da divisão e conquista produz um algoritmo eficiente
se a fase de divisão
e a fase da combinação
forem suficientemente rápidos.
Exemplos
Vejas alguns algoritmos que
usam o método 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.
-
Escreva um algoritmo de divisão e conquista
para encontrar o valor de um elemento máximo
de um vetor A[p .. r]
de números inteiros.
Seja n o número r − p + 1
e C(n) o número de comparações
que seu algoritmo faz entre elementos do vetor.
Escreva a recorrência que C(n) satisfaz.
Exiba a solução (exata) da recorrência
e prove por indução que essa solução está correta.
-
Distância tau de Kendall.
Suponha dadas duas permutações, digamos A[1 .. n]
e B[1 .. n],
de um mesmo conjunto de números.
A distância τ de Kendall
entre A e B
é o número de pares de elementos do conjunto que estão em ordem diferente
em A e B,
ou seja,
o número ⎮X − Y⎮
onde X é o conjunto de todos os pares (A[i], A[j])
tais que i < j
e Y é o conjunto de todos os pares (B[i], B[j])
tais que i < j.
(A definição não é assimétrica pois ⎮X − Y⎮ = ⎮Y − X⎮.)
Escreva uma função eficiente que calcule a distância τ de Kendall
entre A e B.