The element number reaches 100000 and I have to compare it with another vector of 100000, how can I do this with a very high gain gain?
How I'm comparing vectors
for(i = 0; i < teste; i++)
{
for(j = 0; j < teste; j++)
{
if(indice[i] == aux[j])
{
cont++;
}
}
}
You can try to create a hash vector, for example
char hash[0x7FFFFFFF];
If any positive integers are possible.
Initialize the vector,
for (int i = 0; i < 0x7FFFFFFF; ++i)
{
hash[i] = 0;
}
Itere one of your original vectors and use hash to know that number exists in this vector:
for (int i = 0; i < teste; ++i)
{
hash[indice[i]] = 1;
}
Then iterates the second vector, incrementing% with% if hash is already filled,
for (int i = 0; i < teste; ++i)
{
if (hash[aux[i]])
{
++cont;
}
}
In this way complexity becomes O (n), instead of O (n ^ 2), which was your case.
The problem now is that a lot of RAM is used. At least 1 GB of RAM, just for the vector hash ...
So there is a trade-off between algorithmic complexity and spatial complexity, which must always be taken into account.