Dato che due array trovano l'indice k che minimizza la somma A [i] * | B [i] -B [k] |

Question

Mi vengono dati due array che contengono numeri naturali, A e B, e ho bisogno di trovare l'indice k che minimizzi la somma A [i] * | B [i] -B [k] | da i = 0 a n-1. (Entrambi gli array hanno la stessa lunghezza) Ovviamente è facile da fare in O (n^2), ho appena calcolato tutte le somme per tutti i k tra 0 e n-1, ma ho bisogno di una complessità del tempo di esecuzione migliore.

Qualche idea? Grazie!

Answer 1

È possibile eseguire questa operazione nel tempo O (nlogn) innanzitutto ordinando entrambi gli array in base ai valori in B, quindi eseguendo una singola scansione.

volta gli array sono ordinati, quindi B [i]> = B [k] se i> k e B [i] < = B [k] se i < = k, quindi la somma può essere riscritta come:

sum A[i] * abs(B[i]-B[k]) = sum A[i]*(B[i]-B[k]) for i=k..n-1 
          + sum A[i]*(B[k]-B[i]) for i=0..k-1 

    = sum A[i]*B[i] for i=k..n-1 
     - B[k] * sum A[i] for i=k..n-1 
     + B[k] * sum A[i] for i = 0..k-1 
     - sum A[i]*B[i] for i = 0..k-1 

È possibile precalculate tutte le somme in tempo O (n) che poi ti permette di valutare la somma di destinazione in ogni posizione in O (n) e selezionare il valore per k che dà il miglior punteggio.

Answer 2

Credo di poterlo fare O (n log n).

In primo luogo, ordinare l'array B, applicando la stessa permutazione all'array A (e ricordando la permutazione). Questa è la parte O (n log n). Dato che sommiamo tutto il i, l'applicazione della stessa permutazione agli array A e B non modifica il minimo.

Con una matrice ordinata B, il resto dell'algoritmo è in realtà O (n).

Per ogni k, definire un array C _k [i] = | B [i] - B [k] |

(Nota:. Noi non realmente costruire C _k ... Ci sarà solo usarlo come un concetto per facilitare ragionamento)

osservare che la quantità che stiamo cercando di ridurre al minimo (su k) è la somma di A [i] * C _k [i]. Andiamo avanti e dare che un nome:

Definire: S _k = Σ A [i] * C _k [i]

Ora, per un particolare k, che cosa fa C _k Assomiglia a?

Bene, C _k [k] = 0, ovviamente.

Più interessante, dal momento che l'array B è ordinato, possiamo sbarazzarci dei segni di valore assoluto:

• C _k [i] = B [k] - B [i], per 0 < = i < k
• C _k [i] = 0, per i = k
• C _k [i] = B [i] - B [k], k < i < n

Definiamo ancora due cose.

Definizioni: T _k = Σ A [i] per 0 < = i < k

Definizioni: U _k = Σ A [i] per k < i < n

(Cioè, T _k è la somma dei primi elementi k-1 di A. U _k è la somma di tutti tranne i primi k elementi di A.)

L'osservazione chiave: Dato S _k, T _k, e U _k, possiamo calcolare S _{k + 1}, T _{k + 1}, e U _{k + 1} in costante tempo. Come?

T e U sono facili.

La domanda è: come arriviamo da S _k a S _{k + 1}?

Considerare cosa succede a C _k quando si va a C _{k + 1}. Semplicemente aggiungiamo B [k + 1] -B [k] a ogni elemento di C da 0 a k, e sottraiamo la stessa quantità da ogni elemento di C da k + 1 a n (provalo). Ciò significa che dobbiamo solo aggiungere T k * (B [k + 1] - B [k]) e sottrarre U _k * (B [k + 1] - B [k]) per ottenere da S _k a S _{k + 1}.

Algebricamente ... I primi k termini di S _k sono solo la somma da 0 a k-1 di A [i] * (B [k] - B [i]).

I primi k termini di S _{k + 1} sono la somma da 0 a k-1 di A [i] * (B [k + 1] - B [i])

La differenza tra questa è la somma, da 0 a k-1, di (A [i] * (B [k + 1] - B [i]) - (A [i] * (B [k] - B [i]) Calcola i termini A [i] e cancella i termini B [i] per ottenere la somma da 0 a k-1 di A [i] * (B [k + 1] - B [k]), che è solo T _k * (B [k + 1] - B [k]).

Analogamente per gli ultimi termini n-k-1 di S _k.

Poiché possiamo calcolare S , T , e U in tempo lineare, e si può passare da S _k a S _{k + 1} in tempo costante, possiamo calcolare tutti gli S _k in tempo lineare. Quindi, ricordati il ​​più piccolo e hai finito.

Utilizzare l'inverso della permutazione di ordinamento per ottenere lo k per gli array originali.

Answer 3

Ecco la soluzione O (NlogN). Esempio

A 6 2 5 10 3 8 7 
B 1 5 4 3 6 9 7 

1) Innanzitutto ordina i due array crescente dell'ordine dell'elemento di B. A è solo vincolante con B. Dopo sorta, otteniamo

A 6 10 5 2 3 7 
B 1 3 4 5 6 7 

Poiché B sono in ordine ora . Abbiamo

n-1 
sum A[i]|B[i]-B[k]| 
i=0 

k-1     n-1 
=sum A[i](B[k]-B[i])+ sum A[i](B[k]-B[i]) 
i=0     i=k+1 
     k-1  n-1   k-1   n-1 
=B[k](sum A[i] -sum A[i]) - (sum A[i]B[i]- sum A[i]B[i]) 
     i=0  i=k+1  i=0   i=k+1 

2) Calcoliamo somma prefisso matrice A suma = 0 6 16 21 23 26 33

  i=e 
With sumA sum A[i] can be calcuated in O(1) time for any s and e. 
      i=s 

Per la stessa ragione, possiamo calcolare A [i] B [i] La somma del prefisso. Quindi per ogni k, per controllare il suo valore, ci vuole solo O (1) tempo. Quindi la complessità temporale totale è O(NlogN)+O(N).