このアルゴリズムの時間の複雑さを改善しますか？

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の大きさによって、ソートする価値があるかどうかが決まります（入力配列を変更したくない場合など）。