算法 |将 O(N^2) 的复杂性解决为更小的东西？

Question

我有以下数据:

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

输出应该是:

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

输出基于与每个“H”相交的每个“P”。例如:H1 在 P1、P2 和 P3 之间是通用的。

我已经将它解决为 N^2 问题，其中 N 是 P 的数量。有优化空间吗？我能以某种方式将复杂性降低到线性空间吗？

P 的数量最多可达 2000。每个 P 中的 H 数量最多可达 15。

我有这样的(伪代码):

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

Answer 1

它不能比 O(n^2) 更快，因为有输入。

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

输出是每一对H1: [P_i, P_j]其中 i < j这是O(n^2) .但是，如果您只需要像 H1: [P1, P2, P3] H2: [P1] H3: [P1] H4: [P2, P3] 这样的东西作为对您示例的回答，我认为它可以固定。