Ottimizzazione del tempo di funzionamento dell'algoritmo

Question

Sto cercando di trovare un modo per ottimizzare il mio algoritmo in modo tale che il tempo di esecuzione sia O (n²) (Notazione Big O).

L'input è una matrice con n elementi, di soli numeri interi positivi e negativi. Possiamo presumere che l'array sia già ordinato.

Devo determinare: per ogni r (elemento della matrice), se r = s + t, dove s e t sono anche elementi della matrice e possono essere uguali (s == t), o anche zero.

Ho provato a ridurre il numero di elementi che devo controllare controllando se il numero corrente è positivo o negativo, ma il tempo di esecuzione è ancora troppo lungo. Il problema è che sto usando 3 cicli while che significa già un tempo di esecuzione di O (n³) per il caso peggiore.

Ecco il mio codice:

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

È possibile avviare l'ordinamento della matrice O(nlogn) (se non), allora per ogni elemento della matrice è possibile controllare se ci sono due elementi che la somma è uguale al numero di O(n²).

Il codice è in 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; 
} 

L'idea di controllare se ci sono due numeri in un array (deve essere filtrate) che somma un valore specifico viene partono dal minimo (min = 0) e il massimo (max = arr.Length), quindi in ogni iterazione:

• Se la somma è inferiore al numero, aumentare min indice.
• Se la somma è maggiore del numero, diminuire l'indice max.
• Se la somma è uguale al numero, allora si trova una soluzione.
• Se l'indice min raggiunge max, non ci sono soluzioni.

È possibile fare riferimento a questo question/answers per ulteriori dettagli e prove.

complessità temporale per la soluzione globale è O(n²):

• ordinare l'array: O(nlogn).
• Iterare sulla matrice ordinata: O(n).
• Trova due numeri che sommano il valore: O(n).

Quindi, è O(n²) a causa delle chiamate nidificate a FindTwoThatSumN.

Se si desidera, è possibile passare l'indice anziché il numero al metodo FindTwoThatSumN per evitare con un controllo aggiuntivo utilizzare il numero stesso come parte della soluzione.

Answer 2

1. calcolare tutte le possibili somme di s + t e mettere i risultati in un insieme => O (n)
2. iterate su ogni r e controllare se esiste una somma corrispondente a r => O (n) poiché set.contains viene eseguito in tempo costante.