Memorizzare somme a coppie nello spazio lineare

Question

Se abbiamo due array di dimensione n ciascuno e vogliamo ordinare le loro somme, l'approccio ingenuo sarebbe di memorizzare le loro somme nello spazio O (n^2) e ordinarlo in O (n^2 logn) tempo. Supponiamo di avere lo stesso tempo di esecuzione di O (n^2 logn), come potremmo memorizzare le somme nello spazio lineare di O (n)?

Suppongo che non intendiamo archiviare tutte le somme dato che n^2 elementi non rientrano nello spazio n e che stiamo semplicemente stampando tutto in ordine, quindi questo significa che dobbiamo memorizzare dinamicamente gli oggetti? Qualche consiglio?

(questo è un problema compiti a casa)

Answer 1

Il problema, a quanto mi risulta, è che vogliamo trovare le somme

a1 + b1 a1 + b2 ... a1 + bn 
a2 + b1 a2 + b2 ... a2 + bn 
    ...  ... ... ... 
an + b1 an + b2 ... an + bn 

e stamparle in modo ordinato. La restrizione consiste nell'utilizzare solo la memoria O (n) e l'ora O (n^2 log n) nel processo.

Considerare la tabella sopra come n elenchi (righe) di n elementi ciascuno. Se ordiniamo gli array iniziali in modo che a1 <= a2 <= ... <= an e b1 <= b2 <= ... <= bn, ogni elenco è già ordinato. Ora il problema si riduce alla fusione degli elenchi ordinati n.

Per escogitare, pensa a come unire due elenchi ordinati (come in MergeSort), quindi tre elenchi e così via. Estende banalmente la fusione degli elenchi n di lunghezza n ciascuno nelle operazioni n per ciascun elemento di output, per un totale di O (n^3). Ora, ciò che resta da fare è ridurre i tempi di riduzione di ciascun elemento di output su O (log n). Mentre chiedi un suggerimento ma non una soluzione completa, vedi se riesci a gestirlo da solo.

Answer 2

in Python è possibile una cosa del genere:

import heapq 

a = [2, 1, 3] 
b = [4, 6, 5] 

a.sort() 
b.sort() 

def add_to_b(x): 
    for v in b: 
     yield v + x 

for v in heapq.merge(*[add_to_b(x) for x in a]): 
    print v 

Risultato:

5 
6 
6 
7 
7 
7 
8 
8 
9 

L'idea è che noi ordiniamo entrambi gli array. Quindi aggiungendo a b un elemento di a definisce un generatore di numeri in aumento. Quindi creiamo i generatori n e li uniamo usando heapq.merge. Un generatore, rappresentato dalla funzione add in alto, in un momento specifico necessita di spazio costante (spazio necessario per mantenere la posizione corrente in b). heapq.merge ha bisogno di spazio lineare. Quindi abbiamo bisogno di spazio lineare per l'esecuzione dell'algoritmo.

Answer 3

Prima ordinare i 2 array in ordine crescente, la complessità temporale è 2 * O(n*lgn), che può anche essere considerato come O(n*lgn). Quindi utilizzare uno stack per mantenere il minimo n somme.

Come mantenere il minimo n somme? Prima spinta a1 + b1, a1 + b2, a1 + b3, ..., a1 + bn allo heap.Poi per ogni a[i], 1 <= i < n e b[j], 0 <= j < n, spingere a[i] + b[j] e poi pop il più grande:

for(int j=0;j<n;j++) { 
    heap.push_into(a[0] + b[j]); 
} 
for(int i=1;i<n;i++) { 
    for(int j=0;j<n;j++) { 
     heap.push_into(a[i] + b[j]); 
     heap.pop(); // remove the current largest sum in the heap, then the sums remain in the heap are the smallest n sums 
    } 
} 

Poi gli n elementi nel mucchio sono le più piccole somme n.

La complessità temporale è O(n^2 * lgn), la complessità dello spazio è O(n).