Reduzir complexidade quadrática

Programação Java
#1

Não sei se esse é o fórum mais adequado, mas lá vai:

Oi pessoal. Aqui no trabalho, estou desenvolvendo um framework para relacionar campos no banco de dados com métodos. O desempenho é muito ruim: O(n^2). E eu gostaria de tentar otimizar. Colocando de forma genérica, o problema pode ser dado assim:

Tenho um grupo de dados A e um grupo de dados B. Tenho uma função que relaciona A com B. Sei que cada elemento de A se relaciona com zero ou um elementos de B e cada elemento de B se relaciona com zero ou um elementos de A.

Tenho que criar um programa que gere um Map<A, B> desta relação. A solução adotada por enquanto é:

Map<A, B> mapa = ...

for (A a : grupoA) {
    for (B b : grupoB) {
        if (relacao(a, b)) {
            mapa.put(a, b);
            break; // loop interno.
        }
    }
}

return mapa;

O problema é que essa solução é muito lenta, a complexidade é O(N^2). Estava pensando se não existe um jeito de reduzir para O(n . log(n)).

Alguém tem uma idéia?

#2

Ao meu ver, uma fonte de problemas ai é o fato de vc verificar em TODO o grupo B sempre.

[code]
Map<A, B> mapa = …

for (A a : grupoA) {
for (B b : grupoB) {
if (relacao(a, b)) {
mapa.put(a, b);
grupoB.remove(b); // esse cara não sera lido de novo!
break; // loop interno.
}
}
}

return mapa;[/code]

Agora, sem ver a natureza da relação, fica dificil pensar num algoritmo mais interessante.

#3