Độ phức tạp của bộ nhớ của std :: sort() và std :: sort_heap() là gì?

Question

Như trong tiêu đề - độ phức tạp của bộ nhớ là std::sort() và std::sort_heap() là gì? (Sau này đòi hỏi std::make_heap() vì vậy tôi muốn biết sự phức tạp bộ nhớ của nó là tốt.)

Tôi đã thử tìm kiếm trên các trang web này: http://www.cplusplus.com/reference/http://en.cppreference.com/w/ nhưng một trong hai tôi bị mất nó hoặc họ chỉ đề cập đến mức độ phức tạp thời gian. Độ phức tạp của bộ nhớ của các hàm được chỉ định ở bất kỳ đâu (trong tiêu chuẩn C++ hay một số tài liệu khác)? Hoặc có lẽ đó là thực hiện phụ thuộc?

Answer 1

Đối std::sort() Tôi tìm thấy một câu trả lời trên Cboard, trong đó khá nhiều nói:

Chất lượng về vấn đề thực hiện. Các triển khai khác nhau sử dụng bộ nhớ hiệu quả hơn các triển khai khác. Ngoài ra, tiêu chuẩn cho phép các chuyên môn cho std::sort cho các danh mục vòng lặp khác nhau cho phép thực hiện lựa chọn giữa một vài tùy chọn khác nhau, miễn là độ phức tạp (thời gian) phù hợp với các yêu cầu. Sự phức tạp được đưa ra không phải là thời gian, mà là số so sánh. Việc thực hiện có thể thực hiện các hoạt động hoán đổi N³.

Chi phí bộ nhớ cho hầu hết các lần triển khai std::sort sẽ liên quan đến độ sâu đệ quy và số biến cục bộ được lưu trữ trên ngăn xếp cho mỗi cấp đệ quy. Việc triển khai HP/Microsoft STL của std::sort sử dụng Quicksort cho đến khi/trừ khi phát hiện thấy mức đệ quy đang nhận được quá sâu trong trường hợp nó chuyển sang phân loại đống. Nếu kích thước nhỏ, chẳng hạn như 32 hoặc ít hơn, thì nó sẽ sử dụng Insertionsort.

Bạn có thể thấy so sánh các thuật toán, trong Wikipedia page và ước tính độ phức tạp của bộ nhớ.

Tương tự, tôi nghi ngờ rằng hai thuật toán khác rơi vào cùng một trường hợp.