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:

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).

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:
    • 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?

  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 |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| = |X \ Y|.)  Escreva uma função eficiente que calcule a distância τ de Kendall entre AB.

Valid HTML 4.01 Strict Valid CSS!