Hàm find() hiệu quả như thế nào trên lớp std :: map? Liệu nó lặp đi lặp lại thông qua tất cả các yếu tố tìm kiếm chìa khóa như vậy mà nó là O (n), hoặc là nó trong một cây cân bằng, hoặc nó sử dụng một hàm băm hoặc những gì?Độ phức tạp của hàm find() trong std :: map?
Log(n) Nó được dựa trên một cây đen đỏ.
Chỉnh sửa: n dĩ nhiên là số lượng thành viên trong bản đồ.
Mặc dù điều này là đúng mức độ, có một giới hạn trong bản đồ lớn hơn. Nếu bạn đang tìm kiếm các tập dữ liệu rất lớn, tôi khuyên bạn nên xem xét các bộ chứa mảng kết hợp thay thế. –
Đúng là nhật ký (n). Không đúng sự thật nó được dựa trên cây đỏ/đen. Tiêu chuẩn xác định hoạt động để có độ phức tạp tối đa của log (n) và cách hữu hiệu nhất để đạt được điều này là sử dụng cây đỏ/đen (mặc dù đây không phải là yêu cầu). Vì vậy, bạn có giỏ hàng của bạn trước khi con ngựa. –
@OrgnlDave: Nó luôn luôn đúng (không đến một mức độ). –
Nó không lặp lại tất cả các phần tử, nó thực hiện tìm kiếm nhị phân (là O (log (n))). Nó sử dụng toán tử < hoặc một bộ so sánh để thực hiện tìm kiếm.
Nếu bạn muốn bản đồ băm, bạn có thể sử dụng lệnh std :: unordered_map (được thêm vào C++ - 0x), sử dụng hàm băm và trung bình (tùy thuộc vào hàm băm và dữ liệu bạn cung cấp) tìm() sẽ là O (1).
@NicolBolas: Tôi nhớ đọc ở đâu đó rằng nó không phải là cây bắt buộc, nhờ bình luận của bạn. Sửa lỗi anwer của tôi. – fbafelipe
std::map và std::set được thực hiện bởi nhà cung cấp trình biên dịch bằng cách sử dụng cây tìm kiếm nhị phân cao cân bằng (ví dụ: cây đỏ đen, cây AVL).
Như được David chỉ ra một cách chính xác, find sẽ mất thời gian O (log n), trong đó n là số phần tử trong vùng chứa.
Nhưng đó là với các loại dữ liệu nguyên thủy như int, long, char, double, v.v., không phải bằng dây.
Nếu std:string, cho phép nói về kích thước 'm', được sử dụng như chìa khóa, vượt qua chiều cao của cây tìm kiếm nhị phân cân bằng sẽ yêu cầu log n so sánh của khóa trao với một mục của cây.
Khi std::string là chìa khóa của std::map hoặc std::set, find và insert hoạt động sẽ có giá O (m log n), trong đó m là chiều dài của chuỗi cho rằng cần phải được tìm thấy.
Tôi sẽ upvote này cho chỉ ra rằng các so sánh cá nhân không nhất thiết phải O (1). Nhưng sau đó bạn đã thực hiện chỉnh sửa về Java mà tôi không hiểu. Khóa băm được trả về bởi 'hashCode()' không phải là một định danh duy nhất, do đó bạn vẫn cần phải thực hiện so sánh chuỗi O (m) khi so sánh hai khóa. – jogojapan
Ngoài ra, tạo hashcode vẫn là O (m), vì vậy không chỉ là nó không nhanh hơn, sử dụng hashcodes sẽ là _slower_ (giả sử chúng không được lưu trữ) –
@jogojapan Cảm ơn bạn đã chỉ ra java.lang.String.hashCode () điều, sửa chữa câu trả lời của tôi bằng cách loại bỏ phần javaj và gắn bó với câu hỏi được hỏi. Cũng đã nêu ra một [câu hỏi] (http://stackoverflow.com/questions/17569651/are-string-hashcode-in-java-pre-computed) –
Có tài liệu về STL và thường là trạng thái phức tạp. http://www.cplusplus.com/reference/stl/map/find/ –
Xem: [Bảo đảm phức tạp của các thùng chứa tiêu chuẩn] là gì (http://stackoverflow.com/q/181693/14065) –