<分区>
考虑一个维度为 Nx2 的矩阵，其中每一行包含统一 PDF(即概率密度函数)的下限和上限。
我想计算重叠的数量，其中重叠定义为两个 PDF 重叠的情况，例如:
- PDF1:
[2,5] - PDF2:
[3,6] - 两个 PDF 在
[3,5]区间重叠。
显然，如果三个 PDF p1、p2 和 p3 重叠，我计算三个重叠:p1对比 p2，p1 对比 p3，p2 对比 p3。
我创建了以下计算重叠的 MATLAB 代码:
for m = 1:N-1
for k = m+1:N
l1 = dataService.getObjectCoordinate(m,1);
l2 = dataService.getObjectCoordinate(k,1);
u1 = dataService.getObjectCoordinate(m,2);
u2 = dataService.getObjectCoordinate(k,2);
if (l1 <= l2 && l2 <= u1) || (l2 <= l1 && l1 <= u2)
numOverlaps = numOverlaps + 1;
end
end
end
但是，如您所想，这是 O(N^2)，当 N 很大时，这确实很糟糕。我在三个小时前使用 N=10000 开始执行，它仍在运行。
您能否建议一种降低所提出算法复杂性的方法，也许可以排除一些先验比较？
提前致谢。