Algoritmo che controlla se negli array S e T sono interi s e t so s + t = k se k è dato numero

Question

Sto provando a fare un algoritmo che prende due array, S e T di n interi e interi k. L'algoritmo controlla se gli array hanno interi s e t so s + t = k. (S in S e t in T.) L'algoritmo dovrebbe avere il tempo di esecuzione di O (n log n).

Ho tentato di pensare a qualcosa che ordinasse l'array T e usassi il ciclo per passare a S e usassi la ricerca binaria per vedere se trovo intero come k-S [i] per ogni elemento in S. Ma questo avrà sempre tempo di esecuzione maggiore di n log n, penso.

Non cercare qualcuno che scriva il codice. Solo chiedendo qui per avere qualche idea.

Answer 1

Ordinare i due elenchi, questo è O (n log n).

quindi impostare due iteratori. Uno iteratore inizia al basso valore S e va avanti attraverso valori crescenti a S. L'altro iteratore inizia al più alto valorea T e scorre attraverso i valori sempre minore.

Ripetere la seguente:

• se i valori correnti somma di un numero maggiore di k, avanzare l'iteratore T. Questo dovrebbe diminuire la somma.
• se i valori correnti sono pari a un numero inferiore a k, far avanzare l'iteratore S. Questo dovrebbe aumentare la somma.
• se i valori correnti sono pari a k, quindi uscire con esito positivo.

Questa seconda fase dovrebbe causare al massimo 2N anticipi e quindi O (n). Quindi la complessità totale è O (n log n).

Questo ha la stessa complessità della ricerca binaria ripetuta, ma questo algoritmo dovrebbe essere più veloce, soprattutto per il grande n.

Answer 2

L'algoritmo che si è effettivamente specificato ha tempo di esecuzione O (n log n), assumendo che il numero totale di elementi in entrambi gli array sia O (n). Si può vedere questo qui:

• Ordina una delle matrici (O (n log n))
• Per ogni elemento degli altri array: (O (n) iterazioni)
  • fare un binario ricerca per vedere se l'elemento complementare è dell'altra schiera (O (log n))

il primo passo richiede tempo O (n log n), e il secondo stadio consiste di O (n) iterazioni di un algoritmo O (log n), che quindi richiede anche il tempo O (n log n). Poiché O (n log n) + O (n log n) = O (n log n), l'algoritmo viene eseguito nel tempo O (n log n). Quindi sembra che tu abbia esattamente l'algoritmo che stai cercando!

Spero che questo aiuti!

Answer 3

Il tuo approccio sembra corretto; prima ordinando gli array, due operazioni O (n log n), quindi esegui n ricerche binarie, che sono O (log n) ciascuna.

Answer 4

L'ordinamento è O (n log n). Quindi, per ogni O (n) primo elemento, si ha una ricerca O (log n) per un elemento corrispondente. Sembra O (n log n) in totale (poiché O (f) + O (f) = O (f) per qualsiasi funzione f).

Answer 5

Ordinamento entrambi gli array. Passare attraverso di loro in di fronte a direzioni. Se la somma dei due elementi è minore di k, fai avanzare il puntatore "crescente", se è maggiore di k, fai un passo sul puntatore decrescente. Questo metodo potrebbe essere un po 'più lento rispetto all'ordinamento di uno solo degli array, ma il passaggio finale è decisamente più veloce. E probabilmente più corto, perché la parte di testa e di coda dei due array può essere saltata (tagliata via).

Answer 6

Ancora un altro metodo: memorizzare uno degli array in una tabella hash (O (N)). Esegui un passaggio lineare attraverso l'altro (O (N)) e per ogni elem fai una ricerca di k-elem nella tabella hash. Durata totale: 2 * O (N): = O (N). Profitto!