quarta-feira, 10 de outubro de 2012

SUM PROBLEM

Hoje, falaremos de uma família de problema interessante relacionado com vetores. Primeiramente, vamos começar com o 2SUM PROBLEM:
Seja L um vetor de inteiros. Determine se existe dois  elementos distintos x e y em L, tal que x+y = K.
A ideia mais trivial seria um algoritmo O( n*n ) , mas podemos fazer melhor. Se o vetor L estiver ordenado podemos resolver esse problema com complexidade O(n). Da seguinte maneira:

bool sum2(vector <int> v, int n, int K, int &x, int &y){
  int i,j;
  i = 0;
  j = n-1;
  while(i<j){
    if(v[i]+v[j] > K ) j--;
    if(v[i]+v[j] < K ) i++;
    if(v[i]+v[j] ==K ) {
      x = v[i];
      y = v[j];
      return true;
    }
  }
  return false;
}
Se o vetor L não estiver ordenado, podemos resolver esse problema com complexidade O(nlogn). Primeiramente, ordenando o vetor e depois aplicando a ideia acima.

Problema 2 3SUM PROBLEM
Seja L um vetor de inteiros. Determine se existe três  elementos distintos x, y e z em L, tal que x+y +z= K.
Um algoritmo de força bruta simplesmente enumeraria todas O($n^3$) possiveis escolhas de elementos x,y e z e testaria se x+y+z = K. Considerando o vetor ordenado, uma ideia simples seria  para cada par x,y em L e realizar uma busca binária pelo  valor (K-x-y). Neste caso, o algoritmo teria como  complexidade no pior caso O($n^2$ lg n).

Será que podemos encontrar uma solução melhor? A idéia é reduzir este problema ao problema 2SUM. Para cada valor x em L, determine se existe y,z em L tal que y+z=K-x. Este algoritmo tem complexidade O($n^2$). Considerando que para cada valor x em L executamos um algoritmo com complexidade O(n).

bool sum3(vector<int> v, int n, int K, int & x, int &y, int &z ){
  for(int i=0;i<n;i++){
      x = v[i];
      if( sum2(v,n,K-x,y,z) ){
        return true;
      }
  }
  return false;
}
Em teoria da complexidade, este problema deu origem ao conceito 3SUM-díficil.  Acredita-se que o limite inferior no pior caso para qualquer solução para o  problema 3SUM seria  O($n^2$).Gajentaan e Overmars lista uma séries de  problema em geometria computacional que pode ser reduzidos ao problema de  3SUM. Por exemplo,  
Dado n pontos em linhas horizontais dados por y=0,y=1 e y=2, existe uma linha não-horizontal  que passa por três pontos? 
Este problema pode ser reduzido ao 3SUM.
 Exercício:
1. Desenvolva um algoritmo O( $n^3$ ) para 4SUM.
 2. Desenvolva um algoritmo O( $n^2$ log n) para 4SUM.  

Referências: 
http://www.sciencedirect.com/science/article/pii/0925772195000222
http://en.wikipedia.org/wiki/3SUM

2 comentários:

Thalyson disse...

ótimo post, me ajudou muito

Wladimir Araújo Tavares disse...

Sempre bom receber um retorno positivo.