Confronto di tutti gli elementi dell'array - C algoritmo

Question

Ho una matrice m * n e, per ogni riga, ho bisogno di confrontare tutti gli elementi tra di loro. Per ogni coppia che trovo, chiamerò una funzione che sta per eseguire alcuni calcoli.

Esempio:

my_array -> {1, 2, 3, 4, 5, ...} 

I take 1 and I have: (1,2)(1,3)(1,4)(1,5) 
I take 2 and I have: (2,1)(2,3)(2,4)(2,5) 
and so on 

Utilizzando C ho scritto questo:

for (i=0; i<array_length; i++) { 
    for (k=0; k<array_length; k++) { 
     if (i==k) continue; 

      //Do something 
     } 
    } 
} 

Mi chiedevo se posso usare un algoritmo con complessità inferiori.

Answer 1

No, è O (n^2) per definizione [troppo lungo da spiegare qui, ma mi creda (-:]
ma è possibile diminuire il numero di iterazioni della metà:

for (i=0; i<array_length; i++) { 
    for (k=i+1; k<array_length; k++) { // <-- no need to check the values before "i" 
      //Do something 
      //If the order of i and k make a different then here you should: 
      //'Do something' for (i,k) and 'Do something' for (k,i) 
     } 
    } 
} 

Answer 2

No, è possibile ottenere una complessità computazionale inferiore solo se si include la conoscenza del contenuto dell'array e la semantica dell'operazione per ottimizzare l'algoritmo.

Answer 3

Ci ci sono molte cose che potresti fare, ma che sono possibili e che non dipendono dalla natura dell'array e dalla formula applicata. La complessità complessiva probabilmente rimarrà invariata o addirittura aumenterà, anche se il calcolo può essere fatto per andare più veloce, a meno che la formula abbia un dipendenza dalla complessità dei suoi argomenti, nel qual caso può essere possibile ottenere una riduzione della complessità

Inoltre, passare da AO (N^a) a BO (N^b) con b> a (maggiore complessità) può ancora valere la pena di proseguire, per alcuni intervalli di N, se B è sufficientemente più piccolo di A.

In nessun ordine particolare:

• se la matrice ha diversi elementi ripetuti, può essere conveniente utilizzare una funzione di caching:

  funzione risultato (arg1, arg2) { int i = indice (arg1, arg2); // A seconda dei valori, potrebbe essere // qualcosa come arg1 * (MAX_ARG2 + 1) + arg2; se (! Memorizzato [i]) {// memorizzato e i valori sono allocati e inizializzati // da qualche altra parte o in questa funzione utilizzando un flag statico //. memorizzato [i] = 1; valori [i] = true_function (arg1, arg2); } valori di ritorno [i]; }

  Quindi, si dispone di un overhead di memoria proporzionale al numero di coppie diverse di valori disponibili. L'overhead di chiamata può essere O (| arg1 | * | arg2 |), ma in alcune circostanze (ad esempio true_function() è costoso) il risparmio sarà più che compensare la complessità aggiunta.

  • tagliare la formula in pezzi (non possibile per ogni formula) ed esprimere come:

    F (x, y) = G (x) op H (y) op J (x , y)

  quindi, è possibile eseguire un ciclo O (max (M, N)) che precarica G [] e H []. Questo ha anche un costo di memoria O (M + N). È utile solo se la differenza di spesa computazionale tra F e J è significativa. Oppure si potrebbe fare:

  for (i in 0..N) { 
      g = G(array[i]); 
      for (j in 0..N) { 
       if (i != j) { 
        result = f(array[i], array[j], g); 
       } 
      } 
  } 
  

  che porta alcuni della complessità da O (N^2) fino a O (N).

  • le prime due tecniche sono utilizzabili in tandem se G() o H() sono pratici da memorizzare nella cache (gamma limitata di argomento, funzione costosa).

  • trovare una "legge" per collegare F (a, b) con F (a + c, b + d). Quindi è possibile eseguire l'algoritmo di caching in modo molto più efficiente, riutilizzando gli stessi calcoli. Ciò sposta una certa complessità da O (N^2) a O (N) o anche O (log N), così mentre il costo complessivo è ancora quadratico, cresce molto più lentamente, e un limite superiore per N diventa pratico. Se F è esso stesso di un ordine superiore di complessità rispetto a costante in (a, b), questo può anche ridurre questo ordine (come esempio estremo, supponiamo che F sia iterativo in a e/o b).