Улучшить временную сложность этого алгоритма?

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, стоит ли ее сортировать (возможно, скопировав ее, если вы не хотите менять входной массив).