Tìm số liệu thống kê đơn hàng của các tiền tố danh sách chưa được phân loại một cách hiệu quả?

Question

A là một mảng các số nguyên từ 1 đến n theo thứ tự ngẫu nhiên.

Tôi cần truy cập ngẫu nhiên vào yếu tố i thứ lớn nhất của các thành phần j đầu tiên trong ít nhất thời gian đăng nhập.

Những gì tôi đã đi lên với cho đến nay là một ma trận n x nM, nơi mà các yếu tố ở vị trí (i, j) là lớn nhất thứ của j đầu tiên i. Điều này cho phép tôi truy cập ngẫu nhiên theo thời gian, nhưng yêu cầu lưu trữ n^2.

Bằng cách xây dựng, M được sắp xếp theo hàng và cột. Hơn nữa, mỗi cột khác với các nước láng giềng của nó bằng một giá trị duy nhất.

Ai đó có thể đề xuất cách nén M xuống n log(n) không gian hoặc tốt hơn, với log(n) hoặc thời gian truy cập ngẫu nhiên tốt hơn?

Answer 1

Tôi tin rằng bạn có thể thực hiện truy cập trong thời gian O (log (N)), cho thời gian tiền xử lý O (N log (N)) và không gian thêm O (N log (N)). Đây là cách làm.

Bạn có thể tăng thêm một cây đỏ đen để hỗ trợ hoạt động select(i) truy xuất phần tử ở cấp bậc i trong thời gian O (log (N)). Ví dụ: see this PDF hoặc chương thích hợp của Giới thiệu về thuật toán.

Bạn có thể thực hiện một cây đỏ đen (thậm chí được tăng thêm để hỗ trợ select(i)) theo cách chức năng, sao cho hoạt động chèn trả về một cây mới chia sẻ tất cả trừ nút O (log (N)) với cây cũ . Xem ví dụ Purely Functional Data Structures bởi Chris Okasaki.

Chúng tôi sẽ xây dựng một mảng T cây đỏ-đen tăng cường hoàn toàn chức năng, như vậy mà cây T[j] lưu trữ các chỉ số 0 ... j-1 của j yếu tố đầu tiên của A sắp xếp lớn nhất đến nhỏ.

Trường hợp cơ sở: Tại T[0] tạo cây tăng màu đỏ đen chỉ với một nút, có dữ liệu là số 0, là chỉ mục của phần tử lớn thứ 0 trong 1 phần tử đầu tiên của mảng A.

bước Inductive: Đối với mỗi j từ 1 tới N-1, tại T[j] tạo ra một cây đỏ-đen tăng cường bằng cách hoàn toàn chức năng chèn một nút mới với chỉ số j vào cây T[j-1]. Điều này tạo ra tối đa các nút mới O (log (j)); các nút còn lại được chia sẻ với T[j-1]. Điều này có thời gian O (log (j)).

Tổng thời gian để tạo mảng T là O (N log (N)) và tổng không gian được sử dụng cũng là O (N log (N)).

Khi T[j-1] được tạo ra, bạn có thể truy cập vào các yếu tố i lớn thứ của j yếu tố đầu tiên của A bằng cách thực hiện T[j-1].select(i). Điều này có thời gian O (log (j)). Lưu ý rằng bạn có thể tạo T[j-1] một cách lười biếng trong lần đầu tiên cần. Nếu A là rất lớn và j luôn luôn là tương đối nhỏ, điều này sẽ tiết kiệm rất nhiều thời gian và không gian.

Answer 2

Trừ khi tôi hiểu sai, bạn chỉ đang tìm kiếm k-th order statistic của một mảng là tiền tố của mảng khác.

Điều này có thể được thực hiện bằng thuật toán mà tôi cho là được gọi là 'quickselect' hoặc điều gì đó dọc theo các dòng đó. Về cơ bản, nó giống như quicksort:

1. Hãy trục ngẫu nhiên
2. Swap xung quanh các phần tử mảng vì vậy tất cả những cái nhỏ hơn là ở một bên
3. Bạn biết đây là p + phần tử lớn nhất 1th trong đó p là số các phần tử mảng nhỏ hơn
4. Nếu p + 1 = k, đó là giải pháp! Nếu p + 1> k, lặp lại trên subarray 'nhỏ hơn'. Nếu p + 1 < k, lặp lại trên 'mảng con' lớn hơn.

Có mô tả (nhiều) tốt hơn here trong tiêu đề Quickselect và Quicker Select, và cũng thường chỉ trên internet nếu bạn tìm kiếm giải pháp quicksort trật tự thứ k.

Mặc dù thời gian xấu nhất cho thuật toán này là O (n2) như quicksort, trường hợp dự kiến ​​của nó tốt hơn nhiều (cũng giống như quicksort) nếu bạn chọn đúng trục xoay ngẫu nhiên của mình. Tôi nghĩ rằng sự phức tạp không gian sẽ chỉ là O (n); bạn chỉ có thể tạo một bản sao của tiền tố của bạn để bỏ qua thứ tự cho.