Theo em đọc trên mạng thì thì nếu em tìm nếu em dù cú pháp in để tìm phần tử có tồn tại trong set python thì độ phức tạp chỉ có là O(1)
Trong khi đó muốn tìm một số có tôn tại trong set hay không thì theo em search trên mạng dùng cú pháp set.count(x) và em đọc có độ phức tạp là O(log(N))
Có cái thể loại container nào của C++ tìm phần tử chỉ có độ phức tạp là O(1) không ạ :\
Lý do gì tìm phần tử trong Set của C++ có độ phức tạp là O(log(N)) trong khi Python là O(1)?
Không biết Python xài cấu trúc dữ liệu gì, nhưng C++ std::set là 1 red-black tree.
Tuỳ vào mục đích bài toán mà bạn có thể chọn cấu trúc dữ liệu phù hợp. std::unordered_map có thể tìm kiếm phần tử trong O(1), nhưng std::unordered_map là hashmap và có thể tốn bộ nhớ không cần thiết cho vấn đề của bạn.
4 Likes
dạ em cảm ơn, có unodered_map chắc cũng có unodered_set đúng không ạ ^^
Bạn lưu ý viết đúng chính tả tiếng Anh, order, không phải oder để tránh lỗi biên dịch đáng tiếc.
Có unordered_set, và nó là một hash table. Nhưng người ta vẫn dùng set thay vì unordered_set:
3 Likes
Mình mới dạo qua Google và thấy rằng Python implement set() như một hash table, giống như unordered_set của C++. Điều này lý giải vì sao các phần tử trong Python set() không được sắp xếp theo thứ tự tăng dần hay thứ tự từ điển.
3 Likes
Em đọc tài liệu trên thì thấy unordered set cái insert của nó sẽ có độ phức tạp là O(n) khi gặp trường hợp xấu? Em không hiểu là rõ ràng kiểu gì insert cũng là chèn phần tử vào cuối set thôi mà. Thế thì trường hợp xấu với trường hợp tốt là những trườn hợp như thế nào ạ?
Set trong python là 1 dạng hash-table, mỗi index sẽ lưu trữ 1 linked list. Do đó tốc độ tìm “trung bình” là O(1). Trường hợp tệ nhất là tất cả các phần tử trong set cho ra chung hash-value, thì sẽ là O(n).
Do đó, để tạo nên hash-table thì mỗi phần tử của Set phải là immutable (hay hash-able). Và cũng do nó là hash-table nên cấu trúc của nó là unordered.
6 Likes
Bạn nên tìm hiểu về cách hash table hoạt động như thế nào.
Khi insert/ search/ delete 1 phần tử vào hash table, việc đầu tiên luôn là quét toàn bộ các key của hash table trước. Bạn có 1 key k và 1 hash value h cần được insert/ update/ delete vào hash table. Trường hợp tốt là khi bạn quét các key thì gặp ngay k và h. Trường hợp xấu là khi bạn quét tất cả các key rồi mà vẫn không thấy bộ (k, h) đâu, bạn đã duyệt toàn bộ hash table.
5 Likes
Mình nghĩ ý này không chính xác. Hash table là để random access vào index như array. Trường hợp xấu nhất như mình đề cập ở trên là tất cả các key có chung hash value (index), nên phải duyệt hết linked list mới insert/update được phần tử cuối.
Mượn hình trên mạng:
ở đây có 1 set là {20,30,40,50} thì 20 và 30 có chung hash value là 5 và chung 1 linked list
5 Likes
Trường hợp xấu nhất là lúc tăng số ô hash (bucket). Phải duy trì tỉ lệ giữa dữ liệu và số bucket (load factor) để tránh đụng.
Lúc này cần đem dữ liệu ra xếp lại vào các bucket (có khi phải tính lại hàm hash) rồi mới chèn vào dữ liệu mới được.
7 Likes
Dạ em có vẻ hiểu rồi ạ, cảm ơn các Bác nhiều lắm ^^
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?