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:
ótimo post, me ajudou muito
Sempre bom receber um retorno positivo.
Postar um comentário