Cho hai mảng tìm chỉ mục k để thu nhỏ tổng A [i] * | B [i] -B [k] |

Question

Tôi có hai mảng chứa số tự nhiên, A và B, và tôi cần tìm chỉ mục k để thu nhỏ tổng A [i] * | B [i] -B [k] | từ i = 0 đến n-1. (Cả hai mảng đều có độ dài tương tự) Rõ ràng là dễ dàng thực hiện trong O (n^2), tôi chỉ tính tất cả các tổng cho tất cả k giữa 0 và n-1, nhưng tôi cần độ phức tạp thời gian chạy tốt hơn.

Bất kỳ ý tưởng nào? Cảm ơn!

Answer 1

Bạn có thể thực hiện điều này trong thời gian O (nlogn) bằng cách sắp xếp cả hai mảng dựa trên các giá trị trong B, sau đó thực hiện quét đơn.

Khi các mảng được sắp xếp, sau đó B [i]> = B [k] nếu i> k và B [i] < = B [k] nếu i < = k, vì vậy tổng có thể được viết lại là:

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 

bạn có thể precalculate tất cả các khoản tiền trong thời gian O (n) sau đó cho phép bạn đánh giá tổng mục tiêu ở mọi vị trí trong thời gian O (n) và chọn giá trị cho k mang đến cho số điểm tốt nhất.

Answer 2

Tôi tin rằng tôi có thể làm điều này là O (n log n).

Đầu tiên, sắp xếp mảng B, áp dụng cùng hoán vị cho mảng A (và ghi nhớ hoán vị). Đây là phần O (n log n). Vì chúng ta tổng hợp trên tất cả i, việc áp dụng cùng hoán vị cho mảng A và B không thay đổi mức tối thiểu.

Với một mảng được sắp xếp B, phần còn lại của thuật toán thực sự là O (n).

Đối với mỗi k, hãy xác định một mảng C _k [i] = | B [i] - B [k] |

(Lưu ý:. Chúng tôi sẽ không thực sự xây dựng C _k ... Chúng tôi sẽ chỉ cần sử dụng nó như là một khái niệm cho lập luận dễ dàng hơn)

Quan sát rằng số lượng chúng tôi đang cố gắng để giảm thiểu (trên k) là tổng của A [i] * C _k [i]. Chúng ta hãy đi trước và cho rằng một cái tên:

Xác định: S _k = Σ A [i] * C _k [i]

Bây giờ, đối với bất kỳ k Đặc biệt, những gì hiện C _k nhìn?

Vâng, C _k [k] = 0, hiển nhiên.

Nhiều thú vị, vì mảng B được sắp xếp, chúng ta có thể thoát khỏi những dấu hiệu giá trị tuyệt đối:

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

Hãy xác định hai điều nữa.

Định nghĩa: T _k = Σ A [i] 0 < = i < k

Định nghĩa: U _k = Σ A [i] cho k < i < n

(Tức là, T _k là tổng của các thành phần k-1 đầu tiên của A. U _k là tổng của tất cả trừ các phần tử k đầu tiên của A.)

Các quan sát chính: Với S _k, T _k, và U _k, chúng ta có thể tính toán S _{k + 1}, T _{k + 1}, và U _{k + 1} trong liên tục thời gian. Làm sao?

T và U thật dễ dàng.

Câu hỏi đặt ra là, làm thế nào để chúng tôi nhận được từ S _k tới S _{k + 1}?

Hãy xem xét điều gì sẽ xảy ra với C _k khi chúng tôi truy cập C _{k + 1}. Chúng ta chỉ cần thêm B [k + 1] -B [k] vào mọi phần tử của C từ 0 đến k, và chúng ta trừ đi cùng một lượng từ mọi phần tử của C từ k + 1 đến n (chứng minh điều này). Điều đó có nghĩa là chúng ta chỉ cần thêm T _k * (B [k + 1] - B [k]) và trừ U _k * (B [k + 1] - B [k]) để nhận được từ S _k tới S _{k + 1}.

Đại số ... Cụm từ k đầu tiên của S _k chỉ là tổng từ 0 đến k-1 của A [i] * (B [k] - B [i]).

Các điều khoản k đầu tiên của S _{k + 1} là tổng từ 0 đến k-1 của A [i] * (B [k + 1] - B [i])

Sự khác biệt giữa đây là tổng, từ 0 đến k-1, của (A [i] * (B [k + 1] - B [i]) - (A [i] * (B [k] - B [i])) Đưa ra các thuật ngữ A [i] và hủy các từ B [i] để lấy tổng từ 0 đến k-1 của A [i] * (B [k + 1] - B [k]), là chỉ T _k * (B [k + 1] - B [k]).

Tương tự đối với các điều khoản n-k-1 cuối cùng của S _k.

Kể từ khi chúng ta có thể tính toán S , T , và U trong thời gian tuyến tính, và chúng ta có thể đi từ S _k S _{k + 1} trong thời gian liên tục, chúng tôi có thể tính toán tất cả S _k trong thời gian tuyến tính. Vì vậy, làm điều đó, nhớ nhỏ nhất, và bạn đã làm xong.

Sử dụng nghịch đảo của hoán vị sắp xếp để lấy k cho các mảng ban đầu.

Answer 3

Đây là giải pháp O (NlogN). Ví dụ

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

1) Đầu tiên loại hai mảng để tăng trật tự của nguyên tố B. A chỉ được ràng buộc với B. Sau khi sắp xếp, chúng tôi nhận

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

Kể từ B theo thứ tự tại . Chúng tôi có

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) Chúng tôi tính toán tiền tố tổng của mảng Một 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 

Đối với lý do tương tự, chúng ta có thể tính toán A [i] B [i] Tổng tiền tố. Vì vậy, đối với mỗi k, để kiểm tra giá trị của nó, nó chỉ mất O (1) thời gian. Vì vậy, tổng thời gian phức tạp là O(NlogN)+O(N).