Optymalizacja czasu pracy algorytmu

Question

Próbuję znaleźć sposób na zoptymalizowanie mojego algorytmu tak, aby czas działania był równy O (n²) (Big O Notation).

Dane wejściowe to tablica zawierająca n elementów, tylko dodatnich i ujemnych liczb całkowitych. Możemy założyć, że tablica jest już posortowana.

Muszę określić: dla każdego r (elementu tablicy), czy r = s + t, gdzie s i t są również elementami tablicy i mogą być takie same (s == t), lub także zero.

Próbowałem zmniejszyć liczbę elementów, które muszę sprawdzić, sprawdzając, czy aktualny numer jest dodatni czy ujemny, ale czas działania jest nadal zbyt długi. Problem polega na tym, że używam 3 pętli, co oznacza już czas działania O (n³) w najgorszym przypadku.

Tutaj jest kod:

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

można rozpocząć sortowanie tablicy O(nlogn) (jeśli nie), to dla każdego elementu tablicy można sprawdzić, czy istnieją dwa elementy, że suma ta jest równa liczbie w O(n²).

Kod jest w 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; 
} 

Pomysł, by sprawdzić, czy istnieją dwie liczby w tablicy (musi być sortowane), że suma dana wartość jest zacząć od minimum (min = 0) i maksymalna (max = arr.Length), a następnie w każdej iteracji:

• Jeśli suma jest mniejsza niż liczba zwiększa min indeksu.
• Jeśli suma jest większa niż liczba, zmniejsz wartość indeksu max.
• Jeśli suma jest równa liczbie, to znajdziesz rozwiązanie.
• Jeśli indeks min osiągnie max, wówczas nie ma rozwiązania.

Możesz odwołać się do tego question/answers po więcej szczegółów i dowodów.

Czas złożoność dla ogólnego rozwiązania jest O(n²):

• Sortuj tablica: O(nlogn).
• Powtórzyć posortowaną tablicę: O(n).
• Znajdź dwie liczby, które sumują wartość: O(n).

Tak, jest O(n²) z powodu zagnieżdżonych połączeń do FindTwoThatSumN.

Jeśli chcesz, możesz przekazać indeks zamiast numeru do metody FindTwoThatSumN, aby uniknąć dodatkowego sprawdzenia, użyj samego numeru jako części rozwiązania.

Answer 2

1. obliczyć wszystkie możliwe sumy s + t oraz wykorzystanie wyników w zestawie => O (n)
2. iteracyjnego każdy r i sprawdź, czy istnieje suma pasująca do r => O (n) ponieważ set.contains działa w stałym czasie.