11
Cho một mảng sắp xếp các số nguyên, chúng ta có thể xây dựng một mảng được sắp xếp các tổng của tất cả các cặp trong O (n^2) không?Với một mảng được sắp xếp, chúng ta có thể xây dựng một mảng được sắp xếp các tổng của tất cả các cặp trong O (n^2) không?
Một giải pháp tầm thường là xây dựng dãy tổng trong O (n^2) và sau đó sắp xếp nó trong thời gian O (n^2 (log (n^2)) = O (n^2 logn) .
Một giải pháp khác sẽ được xây dựng mảng n sắp xếp các số n mỗi - trong thời gian O (n^2), và hợp nhất chúng trong thời gian O (n^2 logn) thời gian (xem here ví dụ)
. Chúng tôi có thể làm tốt hơn không?
Um, tại sao giải pháp đầu tiên là thời gian O (n^2 (log^2) n)? Không phải là O (n^2 log (n^2)) (= O (n^2 log (n))) để sắp xếp một mảng có độ dài n^2? Hoặc bạn có trong tâm trí sử dụng một cái gì đó nhanh hơn so với phân loại so sánh? –
aka [Phân loại X + Y] (http://cs.smith.edu/~orourke/TOPP/P41.html) –
@DavidEisenstat để vấn đề kết thúc trừ khi chúng ta có thể nghĩ ra giải pháp chưa tồn tại – aaronman