MO417 - Ata de exercícios resolvidos em aula

Aula de 12/03/2009, 5a feira

Livro: Algoritmos, Teoria e Prática - Tradução da 2a edição americana
Capítulo 2 - Conceitos básicos

Exercício 2.3-7:
Descreva um algoritmo de tempo Θ(n lg n) que, dado um conjunto S de n inteiros e outro inteiro x,
determine se existem ou não dois elementos em S cuja soma seja exatamente x.

Resolução:
    SOMA(S, x)
      MERGE_SORT(S)
      p ← 1
      q ← tamanho[S]
      while (p < q)
        if (S[p] + S[q] > x)
          q ← q - 1
        else
          if (S[p] + S[q] < x)
            p ← p + 1
          else
            return TRUE
      return FALSE
Comentários:
O algoritmo SOMA descrito acima pressupõe a existência e faz uso do algoritmo MERGE_SORT
para ordenar, in loco, os elementos do vetor S. Como sabemos, a complexidade do MERGE_SORT é
Θ(n lg n) em seu pior caso.
Já as instruções que seguem o MERGE_SORT (ou seja, o restante do algoritmo SOMA) contribuem
com complexidade Θ(n) para o algoritmo.
Portanto, concluímos que o algoritmo SOMA apresentará a complexidade dominante, Θ(n lg n).

[Redator: Fábio de Souza Azevedo]