Lý Do Gì Tìm Phần Tử Trong Set Của C++ Có độ Phức Tạp Là O(log(N ...

Có thể bạn quan tâm

programmingcomplexityalgorithmpythonc++ duy_duy (duy duy) July 19, 2021, 6:03am #1 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 ạ :\ noname00 (HK boy) July 19, 2021, 6:07am #2 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 duy_duy (duy duy) July 19, 2021, 6:09am #3 dạ em cảm ơn, có unodered_map chắc cũng có unodered_set đúng không ạ ^^ noname00 (HK boy) July 19, 2021, 6:12am #4 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: Why would anyone use set instead of unordered_set? c++, algorithm, data-structures, c++113 Likes noname00 (HK boy) July 19, 2021, 6:16am #5 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. How is set() implemented? python, data-structures, set, cpython3 Likes duy_duy (duy duy) July 19, 2021, 6:24am #6 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 ạ? nitro2 (Nhím) July 19, 2021, 6:49am #7 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 noname00 (HK boy) July 19, 2021, 6:51am #8 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 nitro2 (Nhím) July 19, 2021, 6:54am #9

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 k đâu, bạn đã duyệt toàn bộ hash table

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:

image1090×666 9.27 KB ở đây có 1 set là {20,30,40,50} thì 20 và 30 có chung hash value là 5 và chung 1 linked list5 Likes rogp10 (rogp10) July 19, 2021, 7:08am #10 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 duy_duy (duy duy) July 19, 2021, 7:26am #11 Dạ em có vẻ hiểu rồi ạ, cảm ơn các Bác nhiều lắm ^^