从数字列表中生成所有唯一对,n选择2

Question

我有一个元素列表(让我们说整数),我需要进行所有可能的2对比较.我的方法是O(n ^ 2),我想知道是否有更快的方法.这是我在java中的实现.

public class Pair {
 public int x, y;
 public Pair(int x, int y) {
  this.x = x;
  this.y = y;
 }
}

public List<Pair> getAllPairs(List<Integer> numbers) {
 List<Pair> pairs = new ArrayList<Pair>();
 int total = numbers.size();
 for(int i=0; i < total; i++) {
  int num1 = numbers.get(i).intValue();
  for(int j=i+1; j < total; j++) {
   int num2 = numbers.get(j).intValue();
   pairs.add(new Pair(num1,num2));
  }
 }
 return pairs;
}

请注意,我不允许自配,所以应该有((n(n + 1))/ 2) - n个可能的对.我目前的工作原理,但随着n的增加,我花了很长时间才能得到这对.有没有办法将上面的O(n ^ 2)算法转换为亚二次方？任何帮助表示赞赏.

顺便说一下,我也试过下面的算法,但是当我基准测试时,根据经验,它的性能比我上面的要差.我以为通过避免内循环,这会加快速度.下面这个算法不应该更快吗？我会认为它是O(n)？如果没有,请解释并告诉我.谢谢.

public List<Pair> getAllPairs(List<Integer> numbers) {
 int n = list.size();
 int i = 0;
 int j = i + 1;
 while(true) {
  int num1 = list.get(i);
  int num2 = list.get(j);
  pairs.add(new Pair(num1,num2));

  j++;

  if(j >= n) {
   i++;
   j = i + 1;
  }

  if(i >= n - 1) {
   break;
  }
 }
}

Answer 1

好吧,你不能,对吧？

结果是一个包含n*(n-1)/2元素的列表,无论这些元素是什么,只是为了填充这个列表(比如用零)需要O(n^2)时间,因为n*(n-1)/2 = O(n^2)......