0

假设我有 5 个包含位置（2D 点）的不同长度的列表。我需要计算这 5 个列表之间所有可能的点对的距离，以便过滤距离小于阈值的对，例如 10。

一种天真的方法是在每个列表的每个点上进行循环，并验证是否有一对距离小于 10。

for position in list1
   for position in list2
      for position in list3
         for position in list4
            for position in list5
               list all pairs possible of 5 positions
               calculate distance of each pair
               if (distance < threshold):
                  add pair positions in final result

当我添加更多新的位置列表时，这种方法具有指数复杂性。

另一种方法不是创建一个包含 5 个列表的循环，而是创建所有可能的 2 个列表的 10 个循环（5 个列表的 2 个组合）。因此，如果我添加更多新列表，复杂性会随着组合数量（不是指数）而增加，但我仍然对此不满意。

有没有办法以线性复杂度计算多列表的所有对距离？谢谢

4

0 回答 0