Cho hai std::set s, người ta có thể đơn giản lặp qua cả hai bộ đồng thời và so sánh các phần tử, dẫn đến độ phức tạp tuyến tính. Điều này không hoạt động đối với std::unordered_set giây, bởi vì các phần tử có thể được lưu trữ theo bất kỳ thứ tự nào. Vậy mức phí là bao nhiêu là a == b cho std::unordered_set?Giá đắt như thế nào so sánh hai bộ không theo thứ tự cho sự bình đẳng?
phức tạp của operator== và operator!=:
tuyến tính phức tạp trong trường hợp trung bình. N trong trường hợp xấu nhất, trong đó N là kích thước của vùng chứa.
Xem thêm chi tiết trong §23.2.5 chuẩn, điểm 11:
Đối unordered_set và unordered_map, sự phức tạp của operator== (ví dụ, số lượng các cuộc gọi đến các == điều hành của value_type, để các vị được trả về bởi key_equal(), và đến hasher trả về bởi hash_function()) tỷ lệ với N trong trường hợp trung bình và đến N trong trường hợp xấu nhất, nơi N là a.size().
Trường hợp xấu nhất là O (n²).
Nhưng các bộ không có thứ tự thực tế được sắp xếp theo thứ tự băm. Vì vậy, có thể so sánh các băm (nếu điều này thất bại các bộ không thể bằng nhau) và sau đó xác minh rằng các băm giống nhau (tuyến tính) có các giá trị giống nhau (O (n²) cho các giá trị khác nhau với cùng một băm).
Trong trường hợp tốt nhất, đây là O (n).
Thông thường độ phức tạp có xu hướng O (n) nếu hàm băm "tốt" (các đối tượng khác nhau -> luôn băm khác nhau) và O (n²) nếu hàm băm "xấu" (mọi thứ luôn giống nhau giá trị băm)
"hàm băm là tốt (các đối tượng khác nhau -> luôn băm khác nhau)" -> băm khác nhau có thể đúng ngay cả đối với thuật toán băm khủng khiếp (ví dụ: chuỗi băm lên tới 128 ký tự bằng cách trả về giá trị băm 8 * 128 bit được nhân bản từ chuỗi), nhưng thay đổi thành số nhóm và kết quả là xấu. Khi không có cái nhìn sâu sắc đặc biệt vào đầu vào tạo điều kiện tránh va chạm, một hàm băm tốt của hàm băm thường có các va chạm trong tỷ lệ sử dụng cho các nhóm không sử dụng ... mà vẫn dẫn đến trung bình O (n). –
@TonyDelroy: Cảm ơn bạn đã chỉ ra điều này! Một "băm tốt" không chỉ trả về "các giá trị khác nhau", mà còn "được phân phối tốt" đối với các nhóm (Không gian băm nên đồng nhất và tôn trọng chính các nhóm, chỉ để giảm thiểu tác động bạn đề cập) –
Bạn có cách hiệu quả để kiểm tra tư cách thành viên đã đặt (ví dụ: chúng có được hỗ trợ bởi hashtables) không? – Thilo
Rõ ràng, dễ hiểu, dễ hiểu và hiểu các từ của tiêu chuẩn C++: "Hai vùng chứa không có thứ tự' a' và 'b' so sánh bằng nhau nếu' a.size() == b.size() 'và, cho mọi nhóm khóa tương đương '[Ea1, Ea2)' thu được từ 'a.equal_range (Ea1)', tồn tại một nhóm khóa tương đương '[Eb1, Eb2)' thu được từ 'b.equal_range (Ea1)', sao cho ' khoảng cách (Ea1, Ea2) == khoảng cách (Eb1, Eb2) 'và' is_permutation (Ea1, Ea2, Eb1) 'trả về' true'. Đối với 'unordered_set' ... độ phức tạp của' operator == '... là tỷ lệ với 'N' trong trường hợp trung bình và' N^2' trong trường hợp xấu nhất, trong đó 'N' là' a.size() '." –