CODEWITHSUNDEEP
algorithmtime-complexitybig-o
user1189332
user1189332

Reputation: 1941

Algorithm | Solving O(N^2) complexity to something lesser?

I have the following data:

P1:
    H1, H2, H3
P2:
    H1, H4
P3:
    H1,H4

The output should be:

H1: [P1, P2], [P1, P3], [P2, P3]
H2: [P1]
H3: [P1]
H4: [P2, P3]

The output is based on every 'P's that intersects with every 'H'. Ex: H1 is common between P1, P2 and P3.

I've solved it as an N^2 problem where N is number of P's. Any room for optimisation? Can I reduce the complexity to linear space somehow?

The number of P's can go upto 2000. Number of H's within each P can go upto 15.

I have my (Pseudo-code) something like this:

for(p1 in P) {
  h1 = listOfH(p1);
    for(p2 in P) {
      h2 = listOfH(p2);
      intersections = findIntersectingHs(h1, h2);
      record(intersections, p1, p2);
    }
}

Upvotes: 0

Views: 66

Answers (1)

Michal Kardas
Michal Kardas

Reputation: 19

It can't be faster than O(n^2) because with input. 

P1: H1  
P2: H1  
P3: H1  
....  
P_N: H1

the output is every pair H1: [P_i, P_j] where i < j which are O(n^2). However if you needed only something like H1: [P1, P2, P3] H2: [P1] H3: [P1] H4: [P2, P3] as an answer to your example i think it can be fastened.

Upvotes: 2

Related Questions