java - 从数字列表中生成所有唯一对，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)...