Biorąc pod uwagę dwie tablice, znajdź indeks k, który minimalizuje sumę A [i] * | B [i] -B [k] |

Question

Mam dwie tablice zawierające liczby naturalne, A i B, i muszę znaleźć indeks k, który minimalizuje sumę A [i] * | B [i] -B [k] | od i = 0 do n-1. (Obie macierze mają tę samą długość) Jest to oczywiście łatwe do zrobienia w O (n^2), po prostu obliczam wszystkie sumy dla wszystkich k pomiędzy 0 i n-1, ale potrzebuję lepszej złożoności czasu wykonywania.

Wszelkie pomysły? Dzięki!

Answer 1

Możesz to zrobić w czasie O (nlogn), najpierw sortując obie tablice na podstawie wartości w B, a następnie wykonując pojedyncze skanowanie.

Gdy tablice są posortowane, to B [i]> = B [k], jeśli i> k i B [i] < = B [k], jeśli i < = k, więc suma może być przepisana jako:

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 

można precalculate wszystkich kwot w czasie o (n), który następnie pozwala ocenić sumę docelową na każdej pozycji w o (n) i wybrać wartość dla K, co daje najlepszy wynik.

Answer 2

Wierzę, że mogę to zrobić, to O (n log n).

Najpierw posortuj tablicę , stosując tę ​​samą permutację do macierzy A (i pamiętając o permutacji). To jest część O (n log n). Ponieważ sumujemy wszystkie i, zastosowanie tej samej permutacji do macierzy A i B nie zmienia minimum.

W przypadku posortowanej tablicy , reszta algorytmu jest w rzeczywistości O (n).

Dla każdego k zdefiniuj tablicę C _k [i] = | B [i] - B [k] |

. (Uwaga: Nie będziemy faktycznie konstrukt C _k ... Będziemy go używać tylko jako koncepcja dla łatwiejszego rozumowania)

Zauważ, że ilość staramy się zminimalizować (ponad K) suma A [i] * C _k [i]. Idziemy do przodu i dać tę nazwę:

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

Teraz, dla danego k, co robi C _k wygląda jak?

Cóż, C _k [k] = 0, oczywiście.

Co ciekawsze, ponieważ macierz B jest posortowana, możemy pozbyć bezwzględnych objawów wartość:

• C _k [i] = B [k] - B [i], 0 < = I < K
• C _K [j] = 0 dla i = K
• C _K [j] = B [I] - B [k] dla k < i < n

Zdefiniujmy jeszcze dwie rzeczy.

Definicja T _K = Σ A [i] o 0 < = I < K

Definicja: U _K = Σ A [j] k < i < n

(Oznacza to, że T _k jest sumą pierwszych elementów k-1 A. U _k jest sumą wszystkich elementów oprócz k pierwszych elementów A.)

Kluczem obserwacja: Biorąc S _k T _k i U _k możemy obliczyć przyjmuje S _{k + 1} T _{k + 1} i U _{k + 1} w stałym czas. W jaki sposób?

T i U są łatwe.

Pytanie jest, w jaki sposób dostać się z S _k S _{k + 1}?

Zastanów się, co dzieje się z C _k kiedy idziemy do C _{k + 1}. Po prostu dodajemy B [k + 1] -B [k] do każdego elementu C od 0 do k, i odejmujemy tę samą ilość z każdego elementu C od k + 1 do n (udowodnij to). To oznacza, że ​​musimy dodać T _k * (B [k + 1] - B [k]) i odjąć U _k * (B [k + 1] - B [k]), aby uzyskać od S _k na S _{k + 1}.

Algebraicznie ... Pierwsze warunki K S _k są tylko sumą od 0 do k-1 z A [i] * (B [k] - B [i]).

Pierwsze k warunki S _{k + 1} to suma od 0 do K-1 w A [i] * (B [k + 1] - B [i])

Różnica pomiędzy jest to suma, od 0 do k-1, z (A [i] * (B [k + 1] - B [i]) - (A [i] * (B [k] - B [i]) Wyróżnij warunki A [i] i anuluj warunki B [i], aby otrzymać sumę od 0 do k-1 A [i] * (B [k + 1] - B [k]), która jest tylko T _k * (B [k + 1] - B [k]).

Podobnie jak w przypadku ostatnich warunków n-k-1 S _k.

Ponieważ można obliczyć S , T i U w czasie liniowego i można przejść od S _k S _{k + 1} w stałym czasie, można obliczyć wszystkie S _k w czasie liniowym. Zrób to, pamiętaj o najmniejszych i gotowe.

Użyj odwrotności permutacji sortowania, aby uzyskać k dla oryginalnych tablic.

Answer 3

Oto rozwiązanie O (NlogN). Przykład

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

1) sortowanie dwie tablicę do zwiększenia kolejności elementu B. jest tylko wiązania B. Po rodzaju otrzymujemy

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

Ponieważ B w rzędzie teraz . Mamy

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) obliczamy sumę prefiksu tablicy 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 

Z tego samego powodu, można obliczyć [I] B [j] z sumą prefiksu. Tak więc dla każdego k, aby sprawdzić jego wartość, zajmuje tylko O ​​(1) czas. Kompleksowa złożoność czasu to O(NlogN)+O(N).