java - 将数组中的每个元素与另一个元素相加的有效解决方案

Question

这看起来很琐碎，不是家庭作业问题。

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=0;j<arr.length;j++)
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

这将打印每个元素的所有总和。这是 O(n^2)。

我想知道这是否可以更有效地解决。

Answer 1

由于 A + B 等于 B + A，您可以只检查 index 中初始元素之后的元素i：

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=i;j<arr.length;j++) //Note: j = i, not j = 0
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

还是O(n^2)/2，所以复杂度基本上还是二次的。

Answer 2

您是否关心打印结果的顺序？如果你不这样做，也许你可以拆分任务并查看并行减少。

我没有测试过，但是这些行中有一些东西

public void sum(int[] arr){
for(int i=0;i<arr.length;i++)
{
   for(int j=0;j<arr.length/2;j=+2)
   System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
   System.out.println(arr[i+1]+"+"+arr[j+1]+"+"+"="+(arr[i+1]+arr[j+1]));
}   
}//end of sum function

Answer 3

如果使用稀疏矩阵，则可以更快地添加矩阵。由于 0 + 0 = 0，稀疏矩阵允许您跳过对这些元素执行加法。

否则，正如其他人所说，您也可以很容易地将问题并行化。