Valuta tutte le combinazioni di coppie in un array per una condizione nella complessità temporale di n log n

se hai bisogno di TUTTI i risultati su una condizione arbitraria (diciamo C(a,b) = (sha1(a~c)^sha1(c~a))%2 == 0 con ~ come concatenazione) allora ci sono n * (n-1) / 2 valori che devi produrre che sono tutti indipendenti; quindi no non c'è modo migliore,

ma se il risultato di una coppia ti dice qualcosa sul risultato di un'altra coppia allora quella informazione può essere usata per accelerare le cose. come nel tuo esempio se somma > k quindi ordina e per ogni numero che controlli ciascuno in ordine (avanti o indietro). Al primo vero risultato si aggiungono i numeri rimasti. Questo sarà O(n log n + r) con r numero di risultati veri.

modifica : ripensandoci, puoi utilizzare una ricerca binaria per ciascun numero a trova il primo numero più grande di k-a riducendolo a O(n log n) completamente

In questo modo generale lo spieghi: no, non può essere fatto.

Appena hai bisogno di valutare tutte le combinazioni di coppie hai praticamente un runtime O (n ² ).

Se esiste un modo per escludere alcune combinazioni (ad esempio per un dato elemento, si sa che nessuna combinazione soddisferà la condizione), è possibile ottenere un comportamento di runtime migliore.

Ad esempio, se si conosce il numero più piccolo dell'array essere min , quindi saltare tutti gli elementi e dove e + min > k può aiutarti a ottenere un runtime più efficace (ma non ridurrà il caso peggiore).

Un altro approccio che è utile se non hai bisogno della soluzione migliore, ma "abbastanza buono" è sufficiente, è usare un euristico. Ad esempio, se puoi "indovinare" che un dato elemento è improbabile essere nella combinazione ideale, puoi saltarlo. Anche in questo caso migliorerai le prestazioni, ma potresti perdere la combinazione ideale.

Given an array A of length n and a bound k find all indices (i,j) such that A[i] + A[j] < k.

Questo può essere risolto in O (n log n) .

Il set I di indici (i, j) che stai cercando ha una struttura quando la matrice è ordinata in ordine crescente. Infatti se (i₀, j₀) appartiene a I quindi, ogni volta che i ≤ i₀ e j ≤ j₀ la coppia indice (i, j) appartiene anche a I . Ciò significa che I assomiglia a questo:

...........
++*........
+++........
+++........
+++........
+++........
+++++*.....
++++++.....
++++++++*..
+++++++++..

dove un punto . denota una coppia che non appartiene a I mentre un più + o una stella * denota una coppia appartenente a I . Come vedi, la presenza di un indice denotato + è implicata dalla presenza di un indice denotato da una stella * quindi solo quest'ultimo deve essere cercato.

1. Ordina l'array in O (n log n)

2. Imposta i sull'indice più grande in modo che A [i] ≤ k in O (n) e impostare j a 1 se usi Pascal o 0 se usi un'altra lingua, questo Quest'ultima operazione è O (1) .

3. Se A [i] + A [j] è maggiore di k quindi diminuisci i e prova 3. di nuovo, altrimenti vai al 4.

4. Se A [i] + A [j + 1] è più piccolo di k quindi aumenta j e prova 4. ancora una volta.

5. Abbiamo trovato un punto contrassegnato con * aggiungilo a I e diminuisci i .

6. Se A [i] + A [j + 1] è maggiore di k quindi diminuisci i e prova 6. ancora una volta.

7. Vai a 4.

Non dimenticare di correggere l'algoritmo e aggiungere il controllo dei limiti e condizioni di uscita adeguate. Nella parte ripetitiva 3.-7. l'algoritmo visita solo gli indici che si trovano alla frontiera tra I e il suo complemento. Questa frontiera ha al massimo 2n quindi il costo complessivo di questa esplorazione è O (n) . La parte ripetitiva 3.-7. è solo un modo ingegnoso per dire: visita quella frontiera, ricordando ogni volta che devi cambiare direzione.

Il costo totale dell'algoritmo è quindi O (n log n) + O (n) + O (1) + O (n) = O (n log n) .

P.S .: In realtà l'immagine dovrebbe essere simmetrica attorno alla prima diagonale e l'algoritmo può smettere di esplorare la frontiera quando incontra la diagonale. Questi sono piccoli dettagli.

P.P.S .: Ovviamente, se la tua condizione non ha una struttura, devi esplorare tutte le combinazioni.