Thuật toán kết hợp bộ nhớ thích ứng với bộ nhớ?

Question

Nhiều thuật toán hoạt động bằng cách sử dụng merge algorithm để hợp nhất hai mảng được sắp xếp khác nhau thành một mảng được sắp xếp duy nhất. Ví dụ, cho là đầu vào các mảng

1 3 4 5 8 

và

2 6 7 9 

Các hợp nhất của các mảng sẽ là mảng

1 2 3 4 5 6 7 8 9 

Theo truyền thống, hình như vẫn có hai cách tiếp cận khác nhau để sáp nhập sắp xếp các mảng (lưu ý rằng trường hợp hợp nhất các danh sách liên kết là hoàn toàn khác nhau). Đầu tiên, có các thuật toán phối hợp ngoài địa điểm hoạt động bằng cách cấp phát một bộ đệm tạm thời để lưu trữ, sau đó lưu trữ kết quả của việc hợp nhất trong bộ đệm tạm thời. Thứ hai, nếu hai mảng xảy ra là một phần của cùng một mảng đầu vào, thì có in-place merge algorithms chỉ sử dụng O (1) không gian lưu trữ phụ và sắp xếp lại hai dãy liền kề vào một chuỗi được sắp xếp. Cả hai lớp thuật toán này đều chạy trong thời gian O (n), nhưng thuật toán kết hợp ngoài vị trí có xu hướng có yếu tố không đổi thấp hơn nhiều vì nó không có các yêu cầu bộ nhớ nghiêm ngặt như vậy.

Câu hỏi của tôi là liệu có một thuật toán hợp nhất đã biết có thể "nội suy" giữa hai phương pháp này hay không. Đó là, thuật toán sẽ sử dụng một nơi nào đó giữa O (1) và O (n) bộ nhớ, nhưng bộ nhớ hơn nó có sẵn cho nó, nhanh hơn nó chạy. Ví dụ, nếu chúng ta đo lường số lượng tuyệt đối của mảng đọc/ghi được thực hiện bởi các thuật toán, nó có thể có một thời gian chạy của hình thức ng (s) + f (s), trong đó s là số lượng không gian có sẵn cho nó và g (s) và f (s) là các hàm có nguồn gốc từ lượng không gian đó. Lợi thế của chức năng này là nó có thể cố gắng hợp nhất với nhau hai mảng theo cách hiệu quả nhất có thể cho các ràng buộc về bộ nhớ - bộ nhớ càng nhiều trên hệ thống, bộ nhớ càng sử dụng và (lý tưởng) hiệu năng tốt hơn .

Chính thức hơn, thuật toán sẽ hoạt động như sau. Cho như đầu vào một mảng A bao gồm hai dãy liền kề, sắp xếp, sắp xếp lại các phần tử trong mảng sao cho các phần tử hoàn toàn theo thứ tự sắp xếp. Thuật toán được phép sử dụng không gian bên ngoài, và hiệu suất của nó phải là trường hợp xấu nhất O (n) trong mọi trường hợp, nhưng nên chạy dần dần nhanh hơn với số lượng không gian phụ trợ lớn hơn để sử dụng.

Có ai quen thuộc với một thuật toán loại này (hoặc biết nơi để tìm thấy một mô tả về một?)

Answer 1

ít nhất là theo các tài liệu, các in-place merge function in SGI STL được thích nghi và "phức tạp thời gian chạy của nó phụ thuộc về số lượng bộ nhớ có sẵn ". Mã nguồn có sẵn tất nhiên bạn có thể ít nhất là kiểm tra này.

Answer 2

EDIT: STL có inplace_merge, sẽ thích ứng với kích thước của bộ đệm tạm thời có sẵn. Nếu bộ đệm tạm thời ít nhất là lớn nhất là một trong các mảng con, đó là O (N). Nếu không, nó sẽ tách hợp nhất thành hai hợp nhất phụ và đệ quy. Việc chia sẽ mất O (log N) để tìm phần bên phải của mảng phụ khác để xoay trong (tìm kiếm nhị phân).

Vì vậy, nó chuyển từ O (N) sang O (N log N) tùy thuộc vào lượng bộ nhớ bạn có sẵn.