Tìm tối thiểu A [i]^2 + B [i]^2 khi A và B được sắp xếp

Question

Cho hai mảng A và B độ dài n. A được sắp xếp tăng dần và B được sắp xếp giảm dần. Tìm chỉ mục i mà "sản phẩm" A[i]^2 + B[i]^2 tối thiểu.

Tôi cần giải pháp trong O(log(n)) là độ phức tạp mong muốn.

Ví dụ trường hợp:

>>> A 
[0, 4, 10, 12, 17, 28, 31, 32, 35, 39] 
>>> B 
[39, 34, 34, 31, 27, 23, 19, 11, 3, 2] 

Đây là "sản phẩm" được giảm thiểu bằng i = 4

>>> [A[i]**2 + B[i]**2 for i in range(10)] 
[1521, 1172, 1256, 1105, 1018, 1313, 1322, 1145, 1234, 1525] 
>>> min(range(10), key=lambda i: A[i]**2 + B[i]**2) 
4 

Answer 1

Để chính thức trực giác của Edgar thành một đầu dò di động thực tế thấp hơn bị ràng buộc, xem xét quy định, đối với i trong [1, n] và một số j không biết đến các thuật toán,

X[i] = 2 * (n**2 + i) 
Y[i] = 2 * (n**2 - i) 
A[i] = X[i] + 1 if i == j 
     X[i]  if i != j 
B[i] = Y[i] + 1 if i == j 
     Y[i]  if i != j 

Chúng tôi làm một số phân tích về A[i]**2 + B[i]**2 giả i != j.

A[i]**2 + B[i]**2 == 4 * n**4 + 8 * n**2 * i + 4 * i**2 
         + 4 * n**4 - 8 * n**2 * i + 4 * i**2 
        == 8 * n**4 + 8 * i**2 
        <= 8 * n**4 + 8 * n**2 

Giả sử i == j.

A[i]**2 + B[i]**2 == 8 * n**4 + 8 * n**2 + 8 * i**2 + 2 
        >= 8 * n**4 + 8 * n**2 + 2 

Sau này là luôn là lớn hơn cũ. (Argh, chúng tôi muốn tối thiểu, không phải là tối đa. Ý tưởng về cơ bản giống nhau - chỉ cần giảm một thay vì tăng một - nhưng đại số hơi khác một chút.)

Gia đình của các cặp mảng j khác nhau trông giống nhau ngoại trừ tại j, do đó, thuật toán phải kiểm tra một nửa số chỉ mục trung bình để xác định j, đồng nghĩa với gia đình này để khám phá ra kết quả chính xác.

Answer 2

Dường như với tôi rằng câu trả lời cho câu hỏi của bạn là "KHÔNG" và thuật toán tuyến tính là nhanh nhất.

Về mặt cấu trúc, chúng tôi có thể tạo chuỗi các độ dài bất kỳ có độ dài tối đa ở bất kỳ vị trí ngẫu nhiên nào trong chuỗi đó. Ngoài ra chuỗi các ô vuông được xây dựng trên các trình tự này không có thứ tự, do đó bạn không thể sử dụng các kỹ thuật như tìm kiếm nhị phân phù hợp cho các chuỗi được sắp xếp.

Ví dụ, nếu chúng ta có hai mảng có độ dài 7:

5 8 10 11 12 14 15 
12 11 10 9 7 6 1 

chúng tôi nhận mảng của tổng các bình phương như thế này:

169 185 200 202 193 232 225 

Chúng ta có thể thấy, đó tối đa là 232, nhưng không có cách nào để tìm ra nó ngoại trừ việc lặp lại trên toàn bộ mảng khiến cho chuỗi tổng của các ô vuông được phân loại và nằm ở đâu đó bên trong.

Cũng sử dụng thực tế là một mảng được sắp xếp là vô dụng vì mảng thứ hai có thể tác động rất lớn trong tổng số tiền và không có ý nghĩa gì khi sử dụng tìm kiếm nhị phân trên một mảng cố gắng đánh giá tổng số tiền.

Tôi chắc chắn rằng vấn đề này tương đương với việc tìm kiếm phần tử lớn nhất trong mảng chưa phân loại có giải pháp tuyến tính là nhanh nhất.

Answer 3

Đây là một đối số phản đối đơn giản mà không thể tìm thấy câu trả lời mà không xem xét tất cả các điểm. Tức là, thuật toán cho đối thủ có thể là chuỗi chỉ mục thích ứng để kiểm tra, và đối thủ sẽ luôn điền vào A và B để duy trì ràng buộc đơn điệu và nó sẽ khiến thuật toán không thể trả lời đúng mà không truy vấn vị trí.

Hãy xem xét chỉ góc phần tư bên phải của mặt phẳng 2d, đối với một số N. Đối thủ sẽ chỉ xếp thứ vào vòng tròn đơn vị, cách đều nhau trong tọa độ cực cho tất cả trừ truy vấn cuối cùng. Cuối cùng, đối thủ sẽ đặt mục thứ N truy vấn ngay trong vòng tròn. Do đó chỉ số truy vấn cuối cùng này là câu trả lời đúng. Nếu có ít hơn N truy vấn và thuật toán chọn vị trí được truy vấn, đối thủ sẽ khẳng định rằng một vị trí không được kiểm soát còn lại bên trong vòng tròn, có nghĩa là câu trả lời đúng có khoảng cách nhỏ hơn 1, nhưng thuật toán trả về khoảng cách 1. Nếu thay thế thuật toán chọn một vị trí không được công nhận, đối thủ đặt nó ngay bên ngoài vòng tròn.