Divisão e conquista

A estrutura de muitos algoritmos eficientes usa o paradigma da divisão e conquista. Esse paradigma (ou estratégia de projeto de algoritmos) consiste no seguinte:

Essa estratégia produz um algoritmo eficiente se o processo de divisão e o processo de combinação forem suficientemente rápidos.

Calvin cartoon

Exemplos.  Eis alguns algoritmos que seguem o paradigma 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. ★ O tamanho das instâncias de um certo problema é medido por um parâmetro n. Tenho três algoritmos — A, BC — para o problema:
    • o algoritmo 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);
    • o algoritmo 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);
    • o algoritmo 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?

  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.