Selection of interesting point from long list efficiently

[chloe123]

Hi, I have some codes which are not efficient enough in helping me to get the answer faster but I have no idea which part I can modify to simply make it more efficient

Just to briefly say about my questions so everyone can have an idea of what the code means.(Thanks in advance for those who read the questions)

Q: Tom is looking for a car with high miles per gallon and high horse power.For example:P1--Toyota with MPG=51,HP=134, the P2--Honda with MPG=40,HP=110, P3--Ford Fusion with MPG=41,HP=191,P4--Nissan with MPG=35,HP=195,P5--Volkswagen with MPG=30,HP=140

Since,p2 is worse than p1(in terms of MPG,HP) and p5 worse than p4(MPG,HP), thus they are cancelled. The leftover 3 cars are considered interesting cars.Tom wish to find all interesting cars from the list but there's too many of them. Thus write a program to find this list as fast as possible.(C++)

int SimpleAlgo2 (int &n, int &d, vector< vector<float> > &point)
{
vector<bool> isBest(n+10, true);

for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {

// We will check if point[i] is strictly worse than point[j]
// no need to check if we already know that point[i] is not the best
if (isBest[i]) {
bool worse_somewhere=false; // This variable will be true if p_i is worse than p_j in some coordinate; i.e., there is k such that p_i[k]<p_j[k]

for (int k=0; k<d; k++)
if (point[i][k]<point[j][k])
worse_somewhere=true;
// if point[i] is worse than point[j] at coordinate k then we set worse_somewhere to be true



bool not_better=true; // This variable will be true if p_i is note better than p_j in all coordinate; i.e., for all k, p_i[k]<=p_j[k]
for (int k=0; k<d; k++)
if (point[i][k]>point[j][k])
not_better=false;
// if point[i] is better than point[j], then not_better=true;

// if point[i] is not better than point[j] and point[i] is actually worse in some dimension, then point[i] is not the best
if (worse_somewhere && not_better) {
isBest[i]=false;
//cout << i << " is eliminated" << endl; //Debug
}
}
}
}

// Count the number of interesting points

int count=0;
for (int i=0; i<n; i++)
if (isBest[i])
count++;

[ne555]

> I have no idea which part I can modify to simply make it more efficient
Your approach is O(n^2), it can be done in O(n lg n)

Suppose that you traverse the cars in increasing HP.
The one with the worst HP would need the best MPG in order to be an interesting point.

[chloe123]

Hi, what do u mean by "Your approach is O(n^2), it can be done in O(n lg n)"??
Actually I am treating n as the number of points and d is a 2 dimension(MPG and HP) and the point[i][j] to refer to the jth dimension of point pi.

[tcs]

See: http://en.wikipedia.org/wiki/Big_O_notation
And google for complexity theorie.