From d.cason@gmail.com Wed Mar 10 13:46:52 2010
Date: Wed, 10 Mar 2010 13:46:52 -0300
From: Daniel Cason <d.cason@gmail.com>
Reply-To: mo417_2010s1@googlegroups.com
To: mo417_2010s1@googlegroups.com
Subject: Ata da questão 2.3-7

Sendo S o vetor original e x a soma desejada, o seguinte algoritmo
resolve o problema:

E(S,x){
 S' <- MergeSort(S)
 Para i<-1 to Lenght(S')
   v <- x - S'[i]
   Se BinarySearch(v,S')
     Retorna (v,S'[i])
}
Retorna {}

A complexidade e' de Teta(n lg n), dada pela soma da complexidade do
MergeSort e as no maximo n execucoes da busca binaria em um vetor de
tamanho n (com complexidade lg n cada uma).

Alem desta resposta, outra possivel e' a seguinte. Dados S e x:

MergeSort(S)
i <- 1
j <- Lenght(S)
while (j > i)
  s <- S[i] + S[j]
  if (s = x)
    return (i,j)
  else if (s > x)
    j <- j -1
  else
    i <- i + 1
end
return {}

Realiza-se igualmente o MergeSort, mas a segunda etapa tem complexidade n.
Ela usa a caracteristica do vetor ser ordenado, ou que faz com que,
para i < j, S[i] + S[j-1] <= S[i] + S[j] <= S[i+1] + S[j].

Vale lembrar que a complexidade assimptotica deste algoritmo eh
identica `a do outro, pelo custo da ordenacao via MergeSort.

[]'s

-- 
Daniel Cason

Nota do instrutor: os algoritmos diferem num ponto essencial.  O
primeiro considera valida uma solucao onde um mesmo elemento de S e'
tomado duas vezes, ou seja, ele somado a si mesmo resulta em x, ao
contrariodo segundo algoritmo.  Nao esta' suficientemente claro no
encunciado se este tipo de solucao e' valida.