提高这个算法的时间复杂度？

Question

我创建了这个算法，它所做的就是找到具有相同乘积的整数对，并且这对整数必须不同。乘积不能超过1024，这是我能想到的最简单的方法，请问有什么方法可以提高这个算法的效率和时间复杂度吗？

谢谢

import java.util.ArrayList;

public class Pairs {

    public static void main(String [] args){

        int nums[] = new int[1024];
        for(int i = 1;i<=1024;i++){
            nums[i-1] = i;
        }
        findPairs(nums);

    }

    static void findPairs(int [] nums){


        ArrayList<IntPair> pairs = new ArrayList<IntPair>();
        ArrayList<Products> products = new ArrayList<Products>();

        IntPair tempObject;
        Products tempProduct;
        int tempMultiplication = 0;

        for(int i =0;i<nums.length;i++){

            for(int j=0;j<nums.length;j++){

                tempObject = new IntPair(nums[i],nums[j]);
                pairs.add(tempObject);

                }


            }

        for(IntPair p:pairs){
            tempProduct = new Products(p.x,p.y);

            if(tempProduct.product <= 1024){
                products.add(tempProduct);
            }


        }


        for(int i = 0;i<products.size();i++){

            tempMultiplication = products.get(i).product;

            for(int j = 0;j<products.size();j++){

                 if(products.get(j).product == tempMultiplication)
                 {
                    if(products.get(i).x == products.get(j).x || products.get(i).y == products.get(j).y) {


                     }
                    else if (products.get(i).x == products.get(j).y || products.get(j).x == products.get(j).y || products.get(i).x == products.get(i).y){


                    }
                     else{
                         System.out.println("Matching pair found:("+ products.get(i).x + ","+products.get(i).y+")"  + "("+ products.get(j).x + ","+products.get(j).y+")" );
                     }


                 }


            }

        }


    }


}

Answer 1

您无法提高算法的时间复杂度。它是 O(n^2)，如果您要比较输入中的所有对，这已经是您所能做的最好的了。

但这并不是说你不能改善运行宁时间。并非所有 O(n^2) 算法都同样好；你可以通过让它做更少的工作来让它更快运行；在这种情况下，这基本上意味着跳过检查乘积不相等的数字。

将对放入具有相等乘积的桶中：

Map<Integer, List<int[]>> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
  for (int j = i+1; j < nums.length; ++j) {
    if (nums[i] == nums[j] || nums[i]*nums[j] > 1024) continue;

    map.computeIfAbsent(nums[i]*nums[j], ArrayList::new)
        .add(new int[] {nums[i], nums[j]});
  }
}

然后迭代每个桶中的所有对：

for (List<int[]> list : map.values()) {
  for (int i = 0; i < list.size(); ++i) {
    for (int j = 1; j < list.size(); ++j) {
      System.out.printf(
          "Matching pair found: %s %s%n",
          Arrays.toString(list.get(i)),
          Arrays.toString(list.get(j)));
    }
  }
}

在最坏的情况下，这仍然是 O(n^2)，即所有数字对的积都相等，这意味着对具有相等积的对的迭代只是迭代所有对。不过，我怀疑这是否真的可能，如果所有数字都不相等，检查数字对中的数字是否不同是禁止的。

您可以通过先排序 nums 来节省一些时间，然后 nums[i]*nums[j] > 1024 打破顶部内循环而不是继续；这取决于 nums 的大小是否值得对其进行排序（如果您不想更改输入数组，则可能已复制它）。

提高这个算法的时间复杂度？

Improve time complexity of this algorithm?

java

algorithm

time

complexity-theory