Tối ưu hóa thời gian chạy của thuật toán

Question

Tôi đang cố gắng tìm cách tối ưu hóa thuật toán của mình sao cho thời gian chạy là O (n²) (Ký hiệu Big O).

Dữ liệu nhập là một mảng có phần tử n, chỉ là số nguyên dương và âm. Chúng ta có thể giả định rằng mảng đã được sắp xếp.

Tôi phải xác định: cho mỗi r (phần tử của mảng), cho dù r = s + t, trong đó s và t cũng là phần tử của mảng, và có thể giống nhau (s == t) hoặc cũng không.

Tôi đã cố gắng giảm số lượng thành phần mà tôi phải kiểm tra bằng cách kiểm tra xem số hiện tại là dương hay âm, nhưng thời gian chạy vẫn còn quá dài. Vấn đề là tôi đang sử dụng 3 trong khi vòng lặp đã có nghĩa là một thời gian chạy của O (n³) cho trường hợp xấu nhất.

Đây là mã của tôi:

public static void Checker(int[] array) { 
    List<Integer> testlist = new ArrayList<Integer>(); 
    int i = 0; 
    while (i < array.length) { 
     int current = array[i]; 
     if (attached(current, array)) { 
      testlist.add(current); 
     } 
     i++; 
    } 
} 

public static boolean attached(int current, int[] array) { 
    boolean result = false; 
    int i = 0; 
    while (i < array.length && !result) { 
     int number1 = array[i]; 
     int j = 0; 
     while (j < array.length && !result) { 
      int number2 = array[j]; 
      if (number1 + number2 == current) { 
       result = true; 
      } 
      j++; 
     } 
     i++; 
    } 
    return result; 
} 

Answer 1

Bạn có thể bắt đầu sắp xếp các mảng O(nlogn) (nếu không muốn nói), sau đó cho mỗi phần tử trong mảng, bạn có thể kiểm tra nếu có hai yếu tố mà tổng là tương đương với số lượng trong O(n²).

Mã này là trong C#:

public static bool Solve(int[] arr) 
{ 
    Array.Sort(arr); //If not already sorted 

    foreach (var num in arr) 
     if (!FindTwoThatSumN(arr, num)) 
      return false; 

    return true; 
} 

public static bool FindTwoThatSumN(int[] arr, int num) 
{ 
    int min = 0; 
    int max = arr.Length - 1; 

    while (true) 
    { 
     if (min == max) break; 

     int sum = arr[min] + arr[max]; 

     if (sum < num) min++; 
     if (sum > num) max--; 
     if (sum == num) return true; 
    } 

    return false; 
} 

Ý tưởng để kiểm tra nếu có hai con số trong một mảng (phải được sắp xếp) mà tổng giá trị cụ thể được bắt đầu từ tối thiểu (min = 0) và tối đa (max = arr.Length), sau đó trong mỗi lần lặp lại:

• Nếu tổng nhỏ hơn số, hãy tăng chỉ số min.
• Nếu số tiền lớn hơn số, hãy giảm chỉ số max.
• Nếu tổng bằng bằng số, thì bạn sẽ tìm thấy giải pháp.
• Nếu min chỉ số đạt đến max thì không có giải pháp.

Bạn có thể tham khảo điều này question/answers để biết thêm chi tiết và bằng chứng.

Thời gian phức tạp cho giải pháp tổng thể là O(n²):

• Sắp xếp mảng: O(nlogn).
• Lặp lại trên mảng được sắp xếp: O(n).
• Tìm hai số tổng giá trị: O(n).

Vì vậy, là O(n²) do các cuộc gọi lồng nhau đến FindTwoThatSumN.

Nếu bạn muốn bạn có thể chuyển chỉ mục thay vì số sang phương thức FindTwoThatSumN để tránh bị kiểm tra bổ sung, hãy sử dụng số đó làm một phần của giải pháp.

Answer 2

1. tính toán tất cả các khoản tiền có thể có của s + t và đưa các kết quả trong một tập => O (n)
2. lặp trên mỗi r và kiểm tra xem có số tiền khớp với r => O (n) kể từ set.contains chạy trong thời gian không đổi.