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:

  1. a instância dada do problema é dividida em duas ou mais instâncias menores,
  2. cada instância menor é resolvida usando o próprio algoritmo que está sendo definido,
  3. 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.

Calvin cartoon

Exemplos

Vejas alguns algoritmos que usam o método da divisão e conquista:

Exercícios

  1. ★ 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.
  2. 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.
  3. 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 AB, ou seja, o número XY 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 XY│ = YX.) Escreva uma função eficiente que calcule a distância τ de Kendall entre AB.