Phân tích: Reversort

Mã giả của giải pháp gần như đã được cung cấp trong đề bài. Chúng ta chỉ cần chuyển nó thành hình thức chính thức trong ngôn ngữ lập trình mà mình lựa chọn. Có hai câu lệnh không hoàn toàn trực tiếp trong mã giả được cung cấp. Chúng ta giả định rằng mình lưu trữ \(L\) trong một mảng, để có thể truy cập nhanh vào bất kỳ chỉ số nào bên trong nó.

Thứ nhất là việc tìm chỉ số của phần tử nhỏ nhất trong một mảng con liên tiếp. Có thể có một số hàm thư viện để thực hiện nhiệm vụ này. Ví dụ, trong C++ chúng ta có thể sử dụng min_element, trong Python chúng ta có thể sử dụng index và min để tìm ra phần tử nhỏ nhất. Chúng ta cũng có thể chạy một vòng lặp khác để tìm phần tử nhỏ nhất trong mảng con. Lưu ý rằng các số đầu vào đều khác nhau nên phần tử nhỏ nhất trong mỗi lần lặp là duy nhất.

Thứ hai là đảo ngược một mảng con. Một lần nữa, có thể có một số hàm thư viện để thực hiện nhiệm vụ này. Ví dụ, chúng ta có thể sử dụng hàm thư viện STL reverse cho C++, reversed hoặc reverse hoặc đơn giản là kỹ thuật slicing trong Python. Chúng ta cũng có thể chạy một vòng lặp để đảo ngược mảng con.

Độ dài của mảng con mà chúng ta đang đảo ngược trong bước thứ hai ở trên chính là chi phí của thao tác đảo ngược. Tích lũy các chi phí này sẽ cho chúng ta câu trả lời cuối cùng.

Độ phức tạp

Giải pháp này có độ phức tạp thời gian là \(O(N^2)\). Chúng ta đang chạy một vòng lặp bên ngoài từ \(1\) đến \(N-1\). Bên trong vòng lặp, chúng ta thực hiện hai bước mà mỗi bước đều mất thời gian tuyến tính: tìm giá trị nhỏ nhất và đảo ngược mảng. Do đó, độ phức tạp thời gian là \(O(N^2)\).

Một lưu ý cuối cùng, có những giải pháp cho bài toán này chạy trong thời gian \(O(N \log N)\), nhưng chúng phức tạp hơn nhiều. Bạn có muốn thử tìm một giải pháp như vậy không?

Dựa trên phân tích chính thức của Google Code Jam.