在Java中查找配对时降低时间复杂性

Question

要找到对，通常使用的方法是迭代两个循环，即

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

它需要O(n^2(的时间复杂度，Java中有其他方法可以找到时间复杂度较低的配对吗？

Answer 1

根据您的评论，您实际要做的是将列表中元素的所有成对组合生成为成对列表。

对于长度为N的列表，在要生成的结果列表中会有N^2对。但是您不能构造优于O(N^2)的N^2值列表。无论你使用什么算法。N^2值的列表包含需要分配给…的N^2单元格。。。这意味着要执行(至少(CCD_ 7原语分配操作。

简而言之，你正在寻找的是数学上的不可能。